去掉了原算法中的无穷大值。代码如下：
#include <assert.h> #include <memory.h> #include <stdlib.h> #include <stdio.h> void mergeSort(char arr[], int p, int r); int main() { char arr[]={'5', '2', '4', '7', '1', '8', '3', '2', '6'}; int count = sizeof(arr); mergeSort(arr, 0, count - 1); for(int i=0; i<count; i++) printf("%c", arr[i]); printf("\n"); return 0; } //arr, 0, 6, 9 //p<=q<r void merge(char arr[], int p, int q, int r) { //n1 + n2 = r - p +1 = arr.length int n1 = q - p + 1; //length of left sub array int n2 = r - q; //length of right sub array //me: //let L[1..n1+1] and R[1...n2+1] be new array assert(n1>0); assert(n2>0); assert(p<=q); assert(q<r); assert(arr != 0); assert(p>-1); assert(q>-1); assert(r>-1); printf("merge:start:arr="); for(int i=p; i<=r; i++) printf("%c,", arr[i]); printf("\n"); char * lArr = malloc(n1); char * rArr = malloc(n2); //for i = 1 to n1 // L[i] = A[p+i-1] memcpy(lArr, arr+p, n1); //safe puts("lArr"); for(int i=0; i<n1; i++) printf("%c,", lArr[i]); puts(""); //for j = 1 to n2 // R[i] = A[q+j] //prove:(arr + r) - (arr + q +1) + 1 = n2 ? // =(r-q-1)+1=r-q=n2 memcpy(rArr, arr+q+1, n2); puts("rArr"); for(int i=0; i<n2; i++) printf("%c,", rArr[i]); puts(""); //L[n1+1]=infinite //lArr[n1] = 0; //rArr[n2] = 0; int i = 0; int j = 0; //r-p+1=n=n1+n2=(q-p+1)+r-q)=r-p+1 for(int k=p; k<=r; k++) //loop n times { if(i==n1) { arr[k] = rArr[j]; j++; continue; } if(j==n2) { arr[k] = lArr[i]; i++; continue; } //i<n1 && j<n2 assert(i<n1 && j<n2); if(lArr[i]<=rArr[j]) { arr[k] = lArr[i]; i++; }else { arr[k] = rArr[j]; j++; } /* if(i<n1 && lArr[i]<=rArr[j]) { arr[k] = lArr[i]; i++; } else if(j<n2) { arr[k] = rArr[j]; j++; } else { printf("illegal:i=%d, j=%d, n=%d, n1=%d, n2=%d\n", i, j, r-p+1, n1, n2); //assert(0); } */ } printf("merge:end:arr="); for(int i=p; i<=r; i++) printf("%c,", arr[i]); printf("\n"); free(lArr); free(rArr); } void mergeSort(char arr[], int p, int r) { if(p<r) { int q = (p+r)/2; mergeSort(arr, p, q); mergeSort(arr, q+1, r); merge(arr, p, q, r); } }