歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。值得注意的是歸并排序是一種穩定的排序方法。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。
算法描述
歸并操作的工作原理如下：
第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
第二步：設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
時間復雜度：
時間復雜度為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));
}
}
