归并排序

归并排序具有递归和非递归两种方式：
递归的归并排序代码如下：
 1 #include <iostream>
 2 #include <list>
 3 #include <stack>
 4 using namespace std;
 5 //合并排序的前期判断，将不符合归并排序的数组进行筛除，
 6 //申请归并排序的辅助数组空间
 7 void MergeSort(int *p, int n)
 8 {
 9     void Msort(int *p, int *temp,int left, int right);
10     if(n <= 0 || p == NULL)
11         return;
12     int *temp = new int[n];
13     if(temp == NULL)
14         return;
15     Msort(p, temp, 0, n-1);
16     delete [] temp;
17 }
18 //递归形式的合并排序
19 void Msort(int *p, int *temp, int left, int right)
20 {
21     void Merge(int *, int *, int, int, int);
22     if(left < right)
23     {
24         int leftend = (left + right) / 2;
25         int rightbegin = leftend + 1;
26         Msort(p, temp, left, leftend);
27         Msort(p, temp, rightbegin, right);
28         Merge(p, temp,left, rightbegin, right);
29     }
30 }
31 //将数组中指定长度的两段，按照一定大小进行合并。
32 void Merge(int *p, int *temp, int left, int rightbegin, int right)
33 {
34     int TempArray = rightbegin;
35     int pos = left;
36     int begin = left;
37     while(left < TempArray && rightbegin <= right)
38     {
39         if(p[left] <= p[rightbegin])
40             temp[pos++] = p[left++];
41         else
42             temp[pos++] = p[rightbegin++];
43     }
44     while(left < TempArray)
45         temp[pos++] = p[left++];
46     while(rightbegin <= right)
47         temp[pos++] = p[rightbegin++];
48     while(pos-- >= begin)
49         p[pos] = temp[pos];
50 }
51 
52 int main()
53 {
54     //测试
55     int num = 9;
56     int *p = new int[num];
57     for(int i = 0; i < num; i++)
58         p[i] = 10 - i;
59     for(int i = 0; i < num; i++)
60         cout << p[i] << endl;
61     MergeSort(p,num);
62     for(int i = 0; i < num; i++)
63         cout << p[i] << endl;
64     return 0;
65 }