归并排序

 1 void mergeArray(int *a,int l,int mid,int r,int *temp)
 2 {
 3     int i=l,j=mid+1;
 4     int k=0;
 5     
 6     while(i<=mid&&j<=r)
 7     {
 8         if(a[i]<=a[j])
 9             temp[k++]=a[i++];
10         else
11             temp[k++]=a[j++];
12     }
13     
14     while(i<=mid)
15         temp[k++]=a[i++];
16     while(j<=r)
17         temp[k++]=a[j++];
18     
19     for(int i=0;i<k;i++)
20         a[l+i]=temp[i];    
21 }
22 
23 void mergeSort(int *a,int l,int r,int *temp)
24 {
25     if(l<r)
26     {
27         int mid=(l+r)/2;
28         mergeSort(a,l,mid,temp);
29         mergeSort(a,mid+1,r,temp);
30         mergeArray(a,l,mid,r,temp); 
31     }
32 } 

 1 const int Size = 1000000;
 2 int array[Size];
 3 int arrayCopy[Size];
 4 
 5 void mergeArray(int *a,int l,int mid,int r,int *temp)
 6 {
 7     int i=l,j=mid+1;
 8     int k=0;
 9     
10     while(i<=mid&&j<=r)
11     {
12         if(a[i]<=a[j])
13             temp[k++]=a[i++];
14         else
15             temp[k++]=a[j++];
16     }
17     
18     while(i<=mid)
19         temp[k++]=a[i++];
20     while(j<=r)
21         temp[k++]=a[j++];
22     
23     for(int i=0;i<k;i++)
24         a[l+i]=temp[i];    
25 }
26 
27 void mergeSort(int *a,int l,int r,int *temp)
28 {
29     if(l<r)
30     {
31         int mid=(l+r)/2;
32         mergeSort(a,l,mid,temp);
33         mergeSort(a,mid+1,r,temp);
34         mergeArray(a,l,mid,r,temp); 
35     }
36 } 
37 
38 int main()
39 {
40     int n;
41     cin>>n;
42     for(int i=0;i<n;i++)
43     {
44         cin>>array[i];
45     }
46     mergeSort(array,0,n-1,arrayCopy);
47     for(int i=0;i<n;i++)
48     {
49         cout<<array[i]<<" ";
50     }
51 }