合併排序法 Merge Sort
合併排序法定義
合併演算法與上一篇介紹的快速排序法一樣，都運用了 Devide and Conquer 的概念，基本上分為兩個步驟：分割與整合。首先利用遞迴把原先未排序的陣列平均分割成兩半，直到各邊都只剩下一個元素（上圖紫色方塊），接著排序後再一一整合起來，最後會合併成一個排序後的陣列（上圖綠色區塊）。
分割 （紫色區塊）
- 把大陣列分一半成為兩個小陣列
- 把從上一步驟切好的兩個小陣列再各自分一半
- 重複步驟 2 直到每個小陣列都只剩一個元素
整合 （綠色區塊）
- 排序兩個只剩一個元素的小陣列並將其合併
- 把上一步驟排序好的小陣列合併並排序成一個陣列
- 重複步驟二直到所有小陣列都合併成一個大陣列
讀者比較有疑問的也許會是這個部分：
Q: [2,3,7,16] 跟 [4,9,11,24] 這兩個陣列是如何合併成最終的已排序陣列呢？
A: 因為這兩個陣列在合併前就已經各自完成排序了，因此只要比較各自最左邊的元素的大小，將比較小的元素放進新陣列中，最後就能完成排序囉！其實從一開始只有一個元素要進行合併時就是運用這個方法喔（只有一個元素的陣列視為已排序）！
時間複雜度
最佳：O(n log n)最差：O(n log n)平均：O(n log n)
時間複雜度的部分，我們依然可以分為 “分割” 與 “整合” 兩個步驟來看。
分割：分割含有 n 個元素的陣列需要 (n-1) 次步驟。
合併：若要合併的兩陣列共用 n 個元素，每次排序與合併必須經過 n 次步驟。
如圖所示，總共4個元素的小陣列，因為每次都是比較最左邊的元素，將較小的一項加到新陣列中，因此總共需要 4 個步驟。
接著要考量的是需要經過幾個回合的合併，從上圖的例子可以發現，原先 8 個獨立的元素經過一次合併後變成 4 個小陣列，再經過一次合併後成為兩個陣列，最後兩個陣列再合併形成最終排序過後的一個陣列，如此每次合併都讓下回需要合併的陣列數減少一半，這表示總共需要合併的回合數會是以 2 為底的 log n 次。
因此合併排序法的時間複雜度為：
時間複雜度 = 分割步驟數 + 合併步驟數 = 分割步驟數 + 每回合合併所花步驟數 * 回合總數 = (n-1) + log n * n
而由於時間複雜度只看最高項係數且忽略常數，因此得出的時間複雜度為 O(n log n)。
程式碼範例
const numbers = [27, 34,16, 4, 1, 5, 69, 65, 223, 7, 0];
function mergeSort (array) {
if (array.length === 1) {
return array; };
const length = array.length;
const middle = Math.floor(length / 2);
const left = array.slice(0, middle);
const right = array.slice(middle);
return merge(
mergeSort(left),mergeSort(right)
);
}
function merge(left, right){
const result = [];
let leftIndex = 0;
let rightIndex = 0;
while(leftIndex < left.length && rightIndex < right.length){
if(left[leftIndex] < right[rightIndex]){
result.push(left[leftIndex]);
leftIndex++;
} else{
result.push(right[rightIndex]);
rightIndex++;
}
}
return
result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
const answer = mergeSort(numbers);
