归并排序

归并是建立在归并操作上的一种有效的算法。该算法是采用（Divide and Conquer）的一个非常典型的应用。值得注意的是归并排序是一种的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序，称为2-路归并。

算法描述

归并操作的工作原理如下：

1. 第一步：申请空间，使其大小为两个已经 序列之和，该空间用来存放合并后的序列。
2. 第二步：设定两个 ，最初位置分别为两个已经 序列的起始位置。
3. 第三步：比较两个 所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。

时间复杂度：

为O(nlogn) 这是该算法中最好、最坏和平均的时间性能。 为 O(n) 比较操作的次数介于(nlogn) / 2和nlogn - n + 1。 赋值操作的次数是(2nlogn)。归并算法的 为：0 (n)
归并 比较占用内存，但却效率高且稳定的算法。

代码实现

自顶向上实现：

void MergeSort(int *aux, int *data, int l, int m, int h)
{
	int k=0, i=l, j=m+1;
	
	for(k=l; k<=h; k++)
	{
		if(i>m)  			aux[k]=data[j++];
		else if(j>h) 			aux[k]=data[i++];
		else if(data[i]<data[j])        aux[k]=data[i++];
		else				aux[k]=data[j++];
	}
	for(k=l; k<=h; k++)
		data[k]=aux[k];
}

用递归实现排序的过程(自顶向下归并)

void Sort(int *aux, int *data, int l, int h)
{
	if(l<h)
	{
		int m=l+(h-l)/2;
		Sort(aux, data, l, m);
		Sort(aux, data, m+1, h);
		MergeSort(aux,data, l, m, h);
	}
}

用非递归实现排序的过程(自底向上归并)

void NonRerMerSort(int *aux, int *data, int l, int h)
{
	int i=l, j;
	for(i=l; i<=h; i=2*i)
	{
		for(j=l; j<=h-i; j+=2*i)
			MergeSort(aux, data, j, i+j-1, Min(j+2*i-1,h));
	}
}