淺顯易懂的合併排序法（Merge sort）

淺顯易懂的合併排序法

概念

將陣列切半直至一數，再兩兩比較將小者先排入新序列，此動作稱為合併，重複動做至剩一序列。

實作 (bottom-up)

由於使用botton-up 可以直接使用陣列，所以不必再將陣列切成一塊，只需合併。

1. 建立指標目的是間接性修改資料，如下：a指向arr陣列，而b為排列後代換的。為什麼不直接替換的原因是：欲比較兩序列中左值若大於右值，交換就會破壞合併時的比較。
2. 第一層迴圈是枚舉長度，從序列n個，藉序列大小乘二，至序列只有一個。以此模擬合併後的序列。
3. 第二層迴圈是遍歷兩欲比較序列，當中以指標設置欲比較序列中的數值，start 為左方序列首，mid 為左序列尾、右序列首，high 為右序列尾，start1、start2、end1、end2紀錄當下比較位置、範圍限制。
4. while迴圈是將比較結果存入b，模擬比較後放入。
5. 將值替換。

(程式碼複製： 點擊這裡查看)