Merge Sort

　　是一高等排序演算法，External sort常用的方法之一。
基本概念：與quick sort相類似，皆利用Divide and conquer algorithms來解決問題。就是把一複雜問題拆解成兩個或更多的相同或相似的子問題，直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合併。
　　主要是將原數列拆解成許多小數列，再將已排序的數列做合併。

Principle

使用Divide and conquer algorithms。

需使用額外的空間來儲存中間結果。

Complexity

Time complexity:
Best.Worst.Average case皆為O(n log n)。
　因n筆records須要作log n回合才完成，而每一回合花O(n)time去合併各runs => O(n log n)。
T(n)=T(n/2)+T(n/2)+c*n
=2T(n/2)+c*n => O(n log n)

Space complexity:
　　O(n)。
　額外空間需求來自於暫存每一回合之合併結果之所須空間，等同於input data space。

運算流程

將數列切割至直到只有一個元素。
開始合併，每次合併同時進行排序，合併成排序好的數列。
重複2動作直到全部合併完成。

Stable vs. Unstable sort

Stable。
ex: Input:[5,8][5*,10]
　Output:[5,5*,8,10]

簡易code

MergeSort(void)　　//Iterative版本
//Run:排序好的片段資料。
//Run長度:Run中之記錄個數。
{while (Run1 and Run2 尚未scan完) do
　　{ if p<=q then
　　　{ 輸出p格之值到new run;
　　　　p前進一格;
　　　}
　　　else
　　　{輸出q格之值到new run;
　　　 q前進一格;
　　　}
　　}
　while(Run1 尚未scan完)
　{ copy Run1剩下Data to new run;
　}
　while(Run2 尚未scan完)
　{ copy Run2剩下Data to new run;
　}
}

簡易code

rMergeSort(x:afile,l,u,p:integer)　　//Recursive版本
//sort x[l]~x[u]成一個Run p
{if l>=u then p=l;
　else
　{ mid=(l+u)/2;
　　rMergeSort(x,l,mid,q);
　　rMergeSort(x,mid+1,u,r);
　　rMergeSort(x,q,r,p);
　}
}