归并排序具有递归和非递归两种方式：
递归的归并排序代码如下：
1 #include2 #include 3 #include
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 else42 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 }