版本一：参考《大话数据结构》中的代码实现。
#define MAXSIZE 10
void merging(int* source,int* result, int start, int middle, int end)
{
int i,j,k;
k=start,i=start,j=middle+1;
while(i<=middle && j<=end)
{
if(source[i]<=source[j])
result[k++]=source[i++];
else
result[k++]=source[j++];
}
while(i<=middle)
result[k++]=source[i++]; //注意，此处的result的角标k就已经对应于
while(j<=end) //最终的角标位置。
result[k++]=source[j++];
}
void MSort(int*source, int start, int end, int* result)
{
int middle;
int* temp=(int*)malloc(MAXSIZE*sizeof(int)); //此处说明在递归函数内部是可以申请动态内存的。
if(start==end)
result[start]=source[start];
else //if(start<end)
{
middle = (start+end)/2;
MSort(source,start,middle,temp);//必须要有temp这个中间变量，否则会导致数值赋值混乱。
MSort(source,middle+1,end,temp);
merging(temp,result,start,middle,end);
}
free(temp);
}
bool MergeSort(int* source, int length)
{
if(NULL==source)
return false;
MSort(source,0,MAXSIZE-1,source);
return true;
}
该版本代码存在的两个主要缺点：
（1）需要事先确定数组的大小MAXSIZE;（2）在递归函数需要不断地开辟空间temp，资源占用较多。
版本二：改进了temp的取法，充分利用了资源。
参考博文http://blog.csdn.net/morewindows/article/details/6678165。
//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
bool MergeSort(int a[], int n)
{
int *p = new int[n];
if (p == NULL)
return false;
mergesort(a, 0, n - 1, p);
delete[] p;
return true;
}