本文共 2092 字，大约阅读时间需要 6 分钟。

1.递归法实现

如上图所示，递归排序法就是借助这种思想；

void Merge(int *arr, int begin, int mid ,int end, int *temp){   	//划分为两个区间	int begin1 = begin;	int end1 = mid;	int begin2 = mid + 1;	int end2 = end;	int sub = begin;	while (begin1 <= end1&&begin2<= end2)//两个数组中，较小的元素放入新辅助空间之中	{   		if (arr[begin1] <= arr[begin2])			temp[sub++] = arr[begin1++];		else			temp[sub++] = arr[begin2++];	}	//检查区间之中是否还有剩余的元素	if (begin1 <= end1)		memcpy(temp + sub, arr+begin1, sizeof(int)*(end1 - begin1+1));	if(begin2<=end2)		memcpy(temp + sub, arr+begin2, sizeof(int)*(end2 - begin2 + 1));	//拷贝回原来的空间	memcpy(arr + begin, temp+begin, sizeof(int)*(end - begin + 1));}void MergeR(int *arr, int begin, int end, int *temp){   	if (begin >= end)		return;	//将区间分解为单个元素的区间，单个元素的区间天然有序	int mid = begin + (end - begin) / 2;	MergeR(arr, begin, mid, temp);	MergeR(arr, mid + 1, end, temp);	//进行合并，从下往上，进行合并有序序列	Merge(arr, begin,mid, end, temp);}void MergeSort(int *arr, int begin, int end,int size){   	assert(arr);	int *temp = (int *)malloc(sizeof(int)*size);	MergeR(arr, begin, end, temp);	free(temp);}

2.非递归实现方法

非递归实现的基本思想是和递归一样的，只不过改变了方式，因此我们需要定义一个变量来控制合并的步伐，同时需要严格的控制边界；

void _Merge(int *arr, int begin1, int end1, int begin2,int end2, int *temp){   	int _begin1 = begin1;//保存一份	int sub = begin1;	while (begin1 <= end1&&begin2 <= end2)//两个数组中，较小的元素放入新辅助空间之中	{   		if (arr[begin1] <= arr[begin2])			temp[sub++] = arr[begin1++];		else			temp[sub++] = arr[begin2++];	}	//检查区间之中是否还有剩余的元素	if (begin1 <= end1)		memcpy(temp + sub, arr + begin1, sizeof(int)*(end1 - begin1 + 1));	if (begin2 <= end2)		memcpy(temp + sub, arr + begin2, sizeof(int)*(end2 - begin2 + 1));	//拷贝回原来的空间	memcpy(arr + _begin1, temp + _begin1, sizeof(int)*(end2 - _begin1 + 1));//特别注意，begin的值是会发生改变的}void MergeSortNoR(int *arr, int size){   	assert(arr);	int *temp = (int *)malloc(sizeof(int)*size);	int gap = 1;	while(gap 
   
    = size)//第二组不存在,不需要合并				break;			if (end2 >= size)//第二组存在，但是不完整				end2 = size - 1;			_Merge(arr, begin1, end1, begin2, end2, temp);//区间[i,i+gap-1],[i+gap,i+2*gap-1]					}		gap *= 2;	}	free(temp);}
   

3.特性