[数据结构与算法]c语言 数据结构——归并排序

基本思想

将两个有序子序列合并，得到一个完全有序的序列，即先使每个子序列有序，再使子序列段间有序，再将两个有序表合并成一个有序表。

void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
		return;

	int mid = (left + right) / 2;
	// [left, mid] [mid+1, right] 有序
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);

	// a[left, mid] a[mid+1, right] 归并到tmp数组

	// tmp 数组拷贝回a
	for (int j = left; j <= right; ++j)
	{
		a[j] = tmp[j];
	}
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
	tmp = NULL;
}