【各种排序系列之】归并排序

 1 //将有序数组a[]和b[]合并到c[]中
 2 void MemeryArray(int a[], int n, int b[], int m, int c[])
 3 {
 4     int i, j, k;
 5 
 6     i = j = k = 0;
 7     while (i < n && j < m)
 8     {
 9         if (a[i] < b[j])
10             c[k++] = a[i++];
11         else
12             c[k++] = b[j++]; 
13     }
14 
15     while (i < n)
16         c[k++] = a[i++];
17 
18     while (j < m)
19         c[k++] = b[j++];
20 }

 1 //将有二个有序数列a[first...mid]和a[mid...last]合并。
 2 void mergearray(int a[], int first, int mid, int last, int temp[])
 3 {
 4     int i = first, j = mid + 1;
 5     int m = mid,   n = last;
 6     int k = 0;
 7     
 8     while (i <= m && j <= n)
 9     {
10         if (a[i] <= a[j])
11             temp[k++] = a[i++];
12         else
13             temp[k++] = a[j++];
14     }
15     
16     while (i <= m)
17         temp[k++] = a[i++];
18     
19     while (j <= n)
20         temp[k++] = a[j++];
21     
22     for (i = 0; i < k; i++)
23         a[first + i] = temp[i];
24 }
25 void mergesort(int a[], int first, int last, int temp[])
26 {
27     if (first < last)
28     {
29         int mid = (first + last) / 2;
30         mergesort(a, first, mid, temp);    //左边有序
31         mergesort(a, mid + 1, last, temp); //右边有序
32         mergearray(a, first, mid, last, temp); //再将二个有序数列合并
33     }
34 }
35 
36 bool MergeSort(int a[], int n)
37 {
38     int *p = new int[n];
39     if (p == NULL)
40         return false;
41     mergesort(a, 0, n - 1, p);
42     delete[] p;
43     return true;
44 }