原理

每次数组分成两部分，先把两部分分别排序好，再这两个有序部分归并成一个整体有序部分。通过这个归并思想用递归反复归并即可。

代码实现

void merge(int* arr, int left, int mid, int right)	//归并函数 left左数组索引 mid右数组索引 right右边界索引
{
	int len = right - left + 1;
	int p1 = left;
	int p2 = mid;

	int* arrRes = (int*)malloc(sizeof(int) * len);
	int i = 0;

	while (p1 < mid && p2 < right + 1)
	{
		if (arr[p1] <= arr[p2])	//为了排序稳定，等于的情况要写在这里
		{
			arrRes[i] = arr[p1];
			p1++;
		}
		else
		{
			arrRes[i] = arr[p2];
			p2++;
		}
		i++;
	}

	while (p1 < mid)
	{
		arrRes[i] = arr[p1];
		p1++;
		i++;
	}

	while (p2 < right + 1)
	{
		arrRes[i] = arr[p2];
		p2++;
		i++;
	}

	memcpy(&arr[left], arrRes, sizeof(int) * len);
	free(arrRes);

}

void sort(int* arr, int left, int right)
{
	if (left >= right)	//收敛条件
	{
		return;
	}
	int mid = left + (right - left) / 2;
	sort(arr, left, mid);	//左边排序
	sort(arr, mid + 1, right);	//右边排序
	merge(arr, left, mid + 1, right);	//两边归并
}

评价

很高效的算法，并且可以保持排序稳定，所以python和java内部对对象的排序都是用的这种，只不过还做了一些改进，