合并排序

 1 Mergesort(A[0..n-1])
 2 //递归调用mergesort来对数组A[0..n-1]排序
 3 //输入：一个可排序数组A[0..n-1]
 4 //输出：非降序排列的数组A[0..n-1]
 5 if n>1
 6     copy A[0..[n/2]-1] to B[0..[n/2]-1]
 7     copy A[[n/2]..n-1] to C[0..[n/2]-1]
 8     Mergesort(B[0..[n/2]-1]
 9     Mergesort(C[0..[n/2]-1]
10     Merge(B,C,A)

 1 Merge(B[0..p-1],C[0..q-1],A[0..p+q-1])
 2 //将两个有序数组合并为一个有序数组
 3 //输入：两个有序数组B[0..P-1]和C[0..q-1]
 4 //输出：A[0..p+q-1]中已经有序存放了B和C中的元素
 5 i<-0;j<-0;k<-0
 6 while i<p and j<q do
 7     if B[i]<=C[j]
 8     else A[k]<-C[j];j<-j+1
 9     k<-k+1;
10     if i=p
11          copy C[j..q-1] to A[k..p+1-1]
12     else copy B[i..p-1] to A[k..p+q-1]

 1 result mergeSort(int *intArray,int n){
 2     if(intArray==NULL||n<0){
 3         return fail;
 4     }
 5     if(n==1){
 6         return success;
 7     }
 8     //分离
 9     int leftLength=n/2;
10     int rightLength=n-leftLength;
11 
12     int *leftArray=(int *)malloc(leftLength*sizeof(int *));
13     int *rightArray=(int *)malloc(rightLength*sizeof(int *));
14 
15     copy(intArray,leftArray,0,0,leftLength);
16     copy(intArray,rightArray,leftLength,0,rightLength);
17 
18 
19     //子数组排序
20     mergeSort(leftArray,leftLength);
21     mergeSort(rightArray,rightLength);
22 
23     //合并
24     merge(leftArray,rightArray,intArray,n);
25     return success;
26 }
27 
28 result merge(int *leftArray,int *rightArray,int *intArray,int n){
29     if(leftArray==NULL||rightArray==NULL||intArray==NULL||n<2){
30         return fail;
31     }
32     int leftLength=n/2;
33     int rightLength=n-leftLength;
34 
35     int leftIndex=0;
36     int rightIndex=0;
37     int intIndex=0;
38 
39     while(leftIndex<leftLength&&rightIndex<rightLength){
40         if(leftArray[leftIndex]<=rightArray[rightIndex]){
41             intArray[intIndex]=leftArray[leftIndex];
42             leftIndex++;
43         }else{
44             intArray[intIndex]=rightArray[rightIndex];
45             rightIndex++;
46         }
47         intIndex++;
48     }
49     if(leftIndex==leftLength){
50         copy(rightArray,intArray,rightIndex,intIndex,n-intIndex);
51     }else{
52         copy(leftArray,intArray,leftIndex,intIndex,n-intIndex);
53     }
54     return success;
55 }
56 
57 void copy(int *sourceArray,int *distArray,int sourceStart,int distStart,int length){
58     for(int i=0;i<length;i++){
59         distArray[distStart+i]=sourceArray[sourceStart+i];
60     }
61 }