归并排序

递归方法实现：

//用递归的方法实现归并排序
void mergeSort1(int arr[],int length)
{
	if (length < 2)
	{
		return;
	}
	process(arr, 0, length - 1);
}
//递归分组及归并
void process(int arr[], int L, int R)
{
	//L=R说明只有一个元素，不用分组了
	if (L == R)  
	{
		return;
	}
	int mid = L + ((R - L) >> 1);
	//将数组分为左右两边，排序与归并
	process(arr, L, mid);
	process(arr, mid + 1, R);
	merge(arr, L, mid, R);
}
//归并函数
void merge(int arr[], int L, int M, int R)
{
	int* help = new int[R - L + 1];
	int i = 0;
	int p1 = L;
	int p2 = M + 1;
	while (p1 <= M && p2 <= R)
	{
    //左边的数小于等于右边时拷贝，即优先拷贝左边，起到稳定排序的作用
		help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];

	}
	while (p1 <= M)
	{
		help[i++] = arr[p1++];
	}
	while (p2 <= M)
	{
		help[i++] = arr[p2++];
	}
	for (i = 0; i < R - L + 1; i++)
	{
		arr[L + i] = help[i];
	}
}

非递归方法实现：

//非递归方法实现归并排序
void mergeSort2(int arr[], int length)
{
	//数组只有一个元素时，不用排序
	if (length < 2)
	{
		return;
	}
	int mergeSize = 1; //当前需要归并的数组左边元素个数
	while (mergeSize < length)
	{
		int left = 0;
		while (left< length)
		{
			//mid是左边分组的末尾元素坐标，一共mergeSize个元素，其坐标当然要-1
			int mid = left + mergeSize - 1;
			if (mid >= length)
			{
				break;
			}
			//right是右边分组的末尾元素坐标
			int right = (mid + mergeSize) < (length - 1) ? (mid + mergeSize) : length - 1;
			//归并当前组的元素
			merge(arr, left, mid, right);
			//开始下一组的归并
			left = right + 1;
		}
		//经过以上循环，原数组被分成[length*1.0/(2*mergeSize)]组，这里[]意为向上取整，并且每组都经过归并
		//这里if语句防止length过大时，mergeSize溢出
		if (mergeSize > length / 2)
		{
			break;
		}
		mergeSize <<= 1;
	}
}

归并排序的时间复杂度：N*logN。

常见题目：

（1）在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和。求数组小和。