归并排序：

两个已排序数组的归并操作：每次从两个数组头部取出最小（或最大）的一个元素，出队，加入新数组末端，直到取完，得到由两个已排序数组元素组成的一个新的已排序数组。

把一个未排序数组不断分割，看成许多单元素组成的数组（可以作为有序的），然后不断归并，最后得到一个排序过的数组。这就是归并排序。

O(nlog(n))的时间复杂度，和快排、堆排一样。不过归并排序总是需要额外的空间存储新数组，所以不如快排的。其优点是没有特别糟的情况，最坏时间复杂度还是那么多。

用C语言写了个递归实现的，gcc 4.5.2，归并排序效率和标准库的qsort()差不多，略快一些（20000000随机数：qsort() 4.06s  归并排序 3.98s），还是相当不错的排序算法。感觉递归可以消去，可能再快一些。

void MergeSort (int *a, const int len)
{
	if (len > 2)
	{
		MergeSort (a, len/2);
		MergeSort (a+len/2, len-len/2);

		int *buf = malloc( len * sizeof(int) );
		int i, *p1 = a, *p2 = a+len/2;
		for (i=0;  i<len-1 && p1!=a+len/2 && p2!=a+len;  i++)
			if (*p1 < *p2)
				buf[i] = *p1++;
			else
				buf[i] = *p2++;

		if (p1 != a+len/2)
			memcpy(buf+i, p1, (len-i)*sizeof(int));
		else if (p2 != a+len)
			memcpy(buf+i, p2, (len-i)*sizeof(int));

		memcpy(a, buf, len*sizeof(int));
		free(buf);
	}
	else if (len == 2 && a[0] > a[1])
	{
		int temp = a[0];
		a[0] = a[1];
		a[1] = temp;
	}
}