读《算法导论》我来C语言实现（2）——合并排序

    书上讲的第二个算法是合并排序，采用了分治法的思想，合并法遵照了分治模式，在每一层递归上都有三个步骤：

    分解：将n个元素分成各含n/2个元素的子序列

    解决：用合并排序对两个子序列递归地排序

    合并：合并两个已排序的子序列以得到排序的结果

    在对子序列排序时，其长度为1时递归结束。单个元素被视为是已排好序的。

    其C语言实现如下：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>

void merge(int *A, unsigned int p, unsigned int q, unsigned int r)
{
	unsigned int i, j, k;
	//前半段为A[p..q], 后半段为A[q+1..r]
	int *L = (int *)malloc((q - p + 1 + 1) * sizeof(int));  //q-p+1为前半段元素的个数,外加额外的一个哨兵
	int *R = (int *)malloc((r - q + 1) * sizeof(int));      //r-q为后半段元素的个数，外加额外的一个哨兵
	
	assert((L != NULL) && (R != NULL));

	for (i = 0; i < q - p + 1; i++)
	{
		L[i] = A[p + i];
	}

	for (j = 0; j < r - q; j++)
	{
		R[j] = A[q + 1 + j];
	}

	L[q - p + 1] = INT_MAX;
	R[r - q] = INT_MAX;
	i = j = 0;
	for (k = p; k <= r; k++)
	{
		if (L[i] <= R[j])
		{
			A[k] = L[i];
			i++;
		}
		else
		{
			A[k] = R[j];
			j++;
		}
	}
	free(L);
	free(R);
}

void merge_sort(int *A, unsigned int p, unsigned int r)
{
	if (p < r)
	{
		unsigned int q = (r + p) / 2;
		merge_sort(A, p, q);
		merge_sort(A, q + 1, r);
		merge(A, p, q, r);
	}
}

int main()
{
	int array[] = {5, 10, 2, 3, 9, -1, 3};
	int i;
	merge_sort(array, 0, sizeof(array) / sizeof(int) - 1);
	for (i = 0; i < sizeof(array) / sizeof(int); i++)
	{
		printf("%d ", array[i]);
	}
	return 0;
}