1 //#只完成兩段之間歸併的功能#%
 2 void Merge(int a[], int b[], int low, int mid, int high)
 3 {
 4     int k = low;
 5     int begin1 = low;
 6     int end1 = mid;
 7     int begin2 = mid + 1;
 8     int end2 = high;
 9     while(k <= high )
10     {
11         if(begin1 > end1)
12             b[k++] = a[begin2++];
13         else if(begin2 > end2)
14             b[k++] = a[begin1++];
15         else
16         {
17             if(a[begin1] <= a[begin2])
18                 b[k++] = a[begin1++];
19             else
20                 b[k++] = a[begin2++];
21         }
22     }
23  
24 }
25  
26 void MergePass(int a[], int b[], int seg, int size)
27 {
28     int seg_start_ind = 0;
29     while(seg_start_ind <= size - 2 * seg) //#size - 2 * seg的意思是滿足可兩兩歸併的最低臨界值#%
30     {
31         Merge(a, b, seg_start_ind, seg_start_ind + seg - 1, seg_start_ind + seg * 2 - 1);
32         seg_start_ind += 2 * seg;
33     }
34     //#如果一段是正好可歸併的數量而另一段則少於正好可歸併的數量#%
35     if(seg_start_ind + seg < size)
36         Merge(a, b, seg_start_ind, seg_start_ind + seg - 1, size - 1);
37     else
38         for(int j = seg_start_ind; j < size; j++) //#如果只剩下一段或者更少的數量#%
39             b[j] = a[j];
40 }
41  
42 void MergeSort(int a[], int size)
43 {
44     int* temp = new int[size];
45     int seg = 1;
46     while(seg < size)
47     {
48         MergePass(a, temp, seg, size);
49         seg += seg;
50         MergePass(temp, a, seg, size);
51         seg += seg;
52     }
53 }
54  
55 int main()
56 {
57     int a[] = {3, 5, 3, 6, 4, 7, 5, 7, 4};
58     MergeSort(a, sizeof(a) / sizeof(*a));
59     //#輸出#%
60     for(int i = 0; i < sizeof(a) / sizeof(*a); i++)
61         cout << a[i] << ' ';
62     cout << endl;
63  
64     return 0;
65 }

参考文档：http://zh.wikipedia.org/wiki/归并排序

优质内容筛选与推荐>>
1、[eclipse]java 查看JDK中底层源码
2、C++ Primer 第3章 字符串、向量和数组
3、极客公园
4、求给定三个点的夹角
5、解决Get和Post请求中中文乱码问题