摘要: 引子：這篇文章以前寫過，最近復習排序算法，覺得以前的代碼還可以改進，因此有了此文。

歸并排序算法以O（NlogN）最壞情形運行時間運行，而所使用的比較次數幾乎是最優的。

該算法中最基本的操作是合并兩個已排序的表，這只需要線性的時間，但同時需要分配一個臨時數組來暫存數據。

歸并排序算法可以用遞歸的形式實現，形式簡潔易懂。如果N=1，則只有一個元素需要排序，我們可以什么都不做；否則，遞歸地將前半部分數據和后半部分數據各自歸并排序，然后合并這兩個部分。

歸并排序算法也可以用非遞歸的形式實現，稍微難理解一點。它剛好是遞歸分治算法的逆向思維形式，在使用遞歸分治算法時，程序員只需考慮將一個大問題分成若干個形式相同的小問題，和解的邊界條件，具體如何解決這些小問題是由計算機自動完成的；而非遞歸形式要求程序員從最基本的情況出發，即從解決小問題出發，一步步擴展到大問題。

我這里兩種形式都給出。

另外，很多人在寫遞歸形式的歸并排序算法時，臨時數組是在MergeSort函數中分配的，這使得在  閱讀全文