1 #include <iostream>
 2 #include <cstdlib>
 3 
 4 #define ARR_SIZE 20
 5 #define MIN(x, y) (x)>(y)?(y):(x) 
 6 using namespace std;
 7 
 8 int kk= 0;
 9 
10 void mergeBUsort(int a[]);
11 void merge(int a[], int lo, int mid, int hi);
12 void CreateRandArr(int a[]);
13 void exchange(int *a, int *b);
14 
15 int main()
16 {
17     int a[ARR_SIZE];
18     int i;
19     CreateRandArr(a);
20     mergeBUsort(a);
21     cout << "after sort: " << endl;
22     for(i=0;i<ARR_SIZE;i  )
23     {
24         cout << a[i] << ' ' ;
25     }
26     
27     return 0;
28 }
29 
30 void mergeBUsort(int a[])   
31 {
32     int sz=1;
33     for(sz=1; sz < ARR_SIZE; sz =sz)
34     {
35         /* 下面的for循環(huán)為什么是 ARR_SIZE - sz 而不是 ARR_SIZE - 2sz：如果是后者的話則數(shù)組的最后一段就不能排序了，之所以lo>ARR_SIZE - 2sz還能繼續(xù)歸并，
36         意思是雖然我后面的元素不足2sz個了，但這后面不足2sz個的元素依然可以分為1點幾個序列（一個有序序列有sz個元素），依然要歸并為1個序列
37         而當后面的元素不足sz個時，也就是不到一個sz序列的長度，說明剩下的這不到sz個元素本身就是有序的，所以不用進行歸并 */
38         for(int lo = 0;lo<ARR_SIZE - sz;lo =2*sz)   
39         {
40             merge(a, lo, lo sz-1, MIN(lo 2*sz-1, ARR_SIZE-1));  /* 因為下一次歸并lo是從2sz開始，所以這里hi取lo 2*sz-1而不是lo 2*sz */
41         }
42     }
43 }
44 
45 void merge(int a[], int lo, int mid, int hi)
46 {
47     int i, j=0, k=lo;  /* 對于遞歸調(diào)用的函數(shù)，千萬要注意：每次遞歸調(diào)用里的參數(shù)每次取的都是對應(yīng)當次遞歸的值！例如這里的k值，每次應(yīng)該賦值為lo而不是0！這個錯誤很容易犯 */
48     int ap[hi 1];
49     for(i=0;i<=hi;i  )
50     {
51         ap[i] = a[i];
52     }
53     i = lo;
54     j = mid 1;
55     while(k<=hi)
56     {
57         if(i > mid)a[k] = ap[j  ];
58         else if(j > hi)a[k] = ap[i  ]; 
59         else if(ap[i] <= ap[j]) a[k] = ap[i  ];
60         else if(ap[i] > ap[j]) a[k] = ap[j  ];
61         k  ;
62     }
63 
64     cout << "No."<< kk   << endl;
65 }
66 
67 void CreateRandArr(int a[])
68 {
69     int i;
70     for(i=0;i<ARR_SIZE;i  )
71     {
72         a[i] = rand() % 100;
73         cout <<a[i] << ' ' ; 
74     }
75     cout << endl;
76 }
77 
78 void exchange(int *a, int *b)
79 {
80     int temp;
81     temp = *a;
82     *a = *b;
83     *b = temp;
84 }

?

另一種？

 1 #include <iostream>
 2 #include <cstdlib>
 3 
 4 #define ARR_SIZE 20
 5 
 6 using namespace std;
 7 
 8 int kk= 0;
 9 
10 void mergesort(int a[], int lo, int hi);
11 void merge(int a[], int lo, int mid, int hi);
12 void CreateRandArr(int a[]);
13 void exchange(int *a, int *b);
14 
15 int main()
16 {
17     int a[ARR_SIZE];
18     int i;
19     CreateRandArr(a);
20     mergesort(a, 0, ARR_SIZE -1);
21     cout << "after sort: " << endl;
22     for(i=0;i<ARR_SIZE;i  )
23     {
24         cout << a[i] << ' ' ;
25     }
26     
27     return 0;
28 }
29 
30 void mergesort(int a[], int lo, int hi)   
31 {
32     if(lo >= hi) return;   /* 如果這里沒有等于的話，會陷入無限遞歸 */
33     int mid = lo   (hi -lo)/2;
34     mergesort(a, lo, mid);
35     mergesort(a, mid 1, hi);
36     merge(a, lo, mid, hi);
37 }
38 
39 void merge(int ar[], int lo, int mid, int hi)
40 {
41     int ap[ARR_SIZE];
42     /* 注意下面這三個變量的賦值，對于遞歸調(diào)用的函數(shù)，千萬要注意：每次遞歸調(diào)用里的參數(shù)每次取的都是對應(yīng)當次遞歸的值！
43     每次merge操作的只是ar數(shù)組中的一部分而不是整個數(shù)組，例如這里的m值，每次應(yīng)該賦值為lo而不是0！這個錯誤很容易犯 */
44     int i=lo,j=mid 1,m=lo;    
45     for(int k=0;k<ARR_SIZE;k  )   /* 其實這里的ap可以放在外面聲明，否則每次都要聲明一遍，拷貝也只拷貝lo到hi的值就可以了 */
46     {
47         ap[k] = ar[k];
48     }
49     while(m<=hi)
50     {
51         if(i>mid)ar[m  ]=ap[j  ];
52         else if(j>hi)ar[m  ] = ap[i  ];
53         else if(ap[i]< ap[j])ar[m  ] = ap[i  ];
54         else ar[m  ] = ap[j  ];
55     }
56 
57 
58 }
59 
60 void CreateRandArr(int a[])
61 {
62     int i;
63     for(i=0;i<ARR_SIZE;i  )
64     {
65         a[i] = rand() % 100;
66         cout <<a[i] << ' ' ; 
67     }
68     cout << endl;
69 }
70 
71 void exchange(int *a, int *b)
72 {
73     int temp;
74     temp = *a;
75     *a = *b;
76     *b = temp;
77 }

?