排序算法（2）:遞歸排序的合並排序

遞歸就是函數調用本身，類似於高中數學中的數學歸納法。當找到數組的第n個元素時，有兩種方法。第壹種方法是根據各種公式找到壹般項公式，第二種方法是數學歸納法找到數據項前後兩項的規律。可以說遞歸只需要知道開始時的特殊情況以及過程如何展開。（遞歸:相反，使用了循環，但有時遞歸很困難，但可以使用堆棧來消除遞歸，因此壹些編譯器使用堆棧來實現遞歸。)

合並排序的原理是合並兩個有序數組。兩個有序數的組合比較簡單，通常它可以在壹次遍歷後組合。因此，只要將兩個數組排序，然後合並壹次，就會獲得壹個有序數組。所以，上面的過程已經找到了，假設壹個數組要排序，它可以分成兩個數組，那麽如何確保這兩個數組是有序的。這裏很明顯，問題回到了開頭，即遞歸（調用函數本身）。遞歸不僅要註意過程，還要註意邊界問題，否則可能陷入無限循環甚至坐標會越界。現在（邊界）是，什麽時候可以細分陣列？顯然，也就是說，數組少於兩個。換句話說，大於1的數組就是調用函數本身。