摘要: 引子：這篇文章以前寫過，最近復(fù)習(xí)排序算法，覺得以前的代碼還可以改進，因此有了此文。
歸并排序算法以O(shè)（NlogN）最壞情形運行時間運行，而所使用的比較次數(shù)幾乎是最優(yōu)的。
該算法中最基本的操作是合并兩個已排序的表，這只需要線性的時間，但同時需要分配一個臨時數(shù)組來暫存數(shù)據(jù)。
歸并排序算法可以用遞歸的形式實現(xiàn)，形式簡潔易懂。如果N=1，則只有一個元素需要排序，我們可以什么都不做；否則，遞歸地將前半部分數(shù)據(jù)和后半部分數(shù)據(jù)各自歸并排序，然后合并這兩個部分。
歸并排序算法也可以用非遞歸的形式實現(xiàn)，稍微難理解一點。它剛好是遞歸分治算法的逆向思維形式，在使用遞歸分治算法時，程序員只需考慮將一個大問題分成若干個形式相同的小問題，和解的邊界條件，具體如何解決這些小問題是由計算機自動完成的；而非遞歸形式要求程序員從最基本的情況出發(fā)，即從解決小問題出發(fā)，一步步擴展到大問題。
我這里兩種形式都給出。
另外，很多人在寫遞歸形式的歸并排序算法時，臨時數(shù)組是在MergeSort函數(shù)中分配的，這使得在
閱讀全文