归并排序

归并排序是一种分治算法，首先把一个数组分成两个子数组，然后递归的对两个子数组进行排序，最后把两个子数组合并起来，问题解决……

递归是一种神奇的技术，所谓人理解循环，神理解递归……我觉得有时候递归很好理解，有时候又很不可思议。虽然这里的代码很长，但是理解这个过程比理解插入排序容易。

还是用扑克牌来举例：有一堆乱序的扑克牌让你去排序，为了让事情更有序更容易，你把牌分成两份，让两个小弟先排好序；两个小弟又分别让他们的两个小小弟去排序；最后的小小小小小弟拿到的是一份已经排好序的牌，只有一张；这样就形成了一棵树……每个小弟把手上的牌排好序就交给自己的老大，老大整理好两组牌再上交给自己的老大……最后到你手里的就是两组已经排好序的牌，然后你再整理一下就完事了。

这个所谓的整理就是合并的过程，归并排序的合并过程首先把两个排好序的子数组各复制一份，再依次从两个子数组中选择最小的一个插入原数组，直到取完所有的牌。这里为了简化代码，在两个新数组的后面各自加入一个哨兵元素，也就是最大可能的值，这样就不必每次检查是不是有哪个数组空了。而要排序的总个数我们是知道的。

其实看代码比看上面的废话更简单：

#include <stdio.h>
#include <limits.h>
#include "array_sort.h"

/**
 * @brief Merge two sorted sub-sequences
 *
 * @param array The input array
 * @param p Beginning index number of array.
 * @param q	Middle index number of array, end of the first sub-sequence.
 * @param r Endding index number of array.
 * @note Attention: p <= q < r
 */
static void merge (int *array, int p, int q, int r)
{
	int n1 = q - p + 1;
	int n2 = r - q;
	int i, j, k;

	/* alloc extra 1 slot for sentinel */
	int la[n1 + 1];
	int ra[n2 + 1];

	for (i = 0; i < n1; i++)
	{
		la[i] = array[p + i];
	}

	for (j = 0; j < n2; j++)
	{
		ra[j] = array [q + j + 1];
	}

	la [n1] = INT_MAX;
	ra [n2] = INT_MAX;

	i = 0;
	j = 0;

	for (k = p; k <= r; k++)
	{
		/* even a integer equal to sentiel still works */
		if (la[i] <= ra[j])
		{
			array[k] = la[i];
			i++;
		}
		else
		{
			array[k] = ra[j];
			j++;
		}
	}
}

/**
 * @brief Merge sort for array
 *
 * Divide: Divede the n-element sequence to be sorted into two subsequences
 * of n/2 elements each.
 * Conquer: Sort the two subsequences recursively using merge sort.
 * Combine: Merger the two sorted subsequences to produce the sorted answer.
 *
 * @note Complexity O( n*lg(n) )
 * @param array The array need to be sort
 * @param p Beginning index number of array
 * @param r Ending index number of array
 * @return The sorted array.
 */

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

	return array;
}