1 #include<stdio.h> 2 #include<stdlib.h> 3  4 void Meger(int A[],int p,int q,int r)//A为数组，p,q,r分别为下标 5 { 6     int n1 = q-p+1; //前半部分长。 7     int n2 = r-q;   //后半部分长。 8     //保存左右部分，为后面改变A[]数列做准备 9     int *L = (int *)malloc(sizeof(int)*n1+1);10     int *R = (int *)malloc(sizeof(int)*n2+1);11     int i;12     for(i=1;i<=n1;i++)13     {14         L[i] = A[p+i-1];15     }16     for(i=1;i<=n2;i++)17     {18         R[i] = A[q+i];19     }20 21     i = 1;22     int j=1;23     int k = p;24     while((i<=n1)||(j<=n2))25     {26         if(L[i]<=R[j])27         {28             A[k] = L[i];29             i++;30             k++;31         }32         else{33             A[k] = R[j];34             j++;35             k++;36         }37     }38     while(i<=n1)39     {40         A[k] = L[i];41         k++;42         i++;43     }44     while(j<=n2)45     {46         A[k] = R[j];47         k++;48         j++;49     }50 }51 52 void Megere_Sort(int A[],int p,int r)53 {54     if(p<r)55     {56         int q = (p+r)/2;57         Megere_Sort(A,p,q);58         Megere_Sort(A,q+1,r);59         Meger(A,p,q,r);60     }61 }62 63 int main()64 {65     int A[10] = {5,8,1,3,4,8,5,6,7,8};66     Megere_Sort(A,0,9);67     int i;68     for(i=0;i<10;i++)69     {70         printf("%d ",A[i]);71     }72     return 0;73 }