归并排序

归并排序（Merge Sort）是一种分治算法（Divide and Conquer），它将数组分成两半，分别对它们进行排序，然后将排序好的两半合并在一起。

递归版本

避免重复 malloc 空间，定义子函数来执行递归，大致思想：类似于二叉树的后根遍历，递归的对左子树和右子树进行归并，下面示意图展示第一次归并过程；归并排序需要开辟额外的数组空间，用以存放每次归并操作后的结果。

其他排序基本只能应用于内存上的排序，而归并排序可以解决在磁盘中的外排序问题。

//递归版本子函数
void _MergeSort(int* a, int begin, int end, int* tmp) {
	//递归出口
	if (begin == end) {
		return;
	}

	int mid = (begin + end) / 2;
	// [begin,mid] [mid+1,end]
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid+1, end, tmp);

	//至此，将左右区间中的共 2 个及以上的元素进行归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;

	int i = begin;
	while (begin1 <= end1 && begin2 <= end2) {
		//如果相等，保持算法稳定性
		if (a[begin1] <= a[begin2]) {
			tmp[i++] = a[begin1++];
		}
		else {
			tmp[i++] = a[begin2++];
		}
	}
	//至此，需要归并的2个区间，已完成一个，处理另一个
	while (begin1 <= end1) {
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2) {
		tmp[i++] = a[begin2++];
	}

	//每次归并都拷贝到原数组一遍，指针要加上 begin
	memcpy(a+begin, tmp+begin, sizeof(int) * (end - begin + 1));
}

//归并排序_递归
void MergeSort(int* a, int begin, int end) {
	//区间不存在或只有一个元素
	if (begin >= end) {
		return;
	}

	int* tmp = (int*)malloc(sizeof(int) * (end - begin + 1));
	if (tmp == NULL) {
		perror("malloc failed");
		return;
	}
	
	_MergeSort(a, begin, end, tmp);

	free(tmp);
}

非递归版本

大致思想：非递归版本中使用局部变量 gap ，进行分组，然后两两归并

需要注意，如果数组元素数量不是每组中 gap 的倍数，那么肯定会出现越界访问的情况，所以需要对越界的区间访问进行修正

//归并排序_非递归
void MergeSortNonR(int* a, int n) {
	int* tmp = (int*)malloc(sizeof(int) * n);

	int gap = 1;
	while (gap < n) {
		int j = 0;
		for (int i = 0; i < n; i += 2 * gap) {

			//仍然是每 2 组归并
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + gap * 2 - 1;

			// 修正
			if (end1 >= n || begin2 >= n)
			{
				break;
			}

			if (end2 >= n)
			{
				end2 = n - 1;
			}

			while (begin1 <= end1 && begin2 <= end2) {
				if (a[begin1] <= a[begin2]) {
					tmp[j++] = a[begin1++];
				}
				else {
					tmp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1) {
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2) {
				tmp[j++] = a[begin2++];
			}

			//每组归并都执行拷贝
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
			gap *= 2;
		}
	}
	free(tmp);
}