（此為Wilsen Ren在Udemy開設之線上課程「資料結構與演算法 (JavaScript)」學習筆記，另有部分內容為自行補充，將持續隨著學習進度更新，若內容有誤，歡迎留言指正！）合併排序（merge sort）
進階排序演算法的一種，以「分治法（divide and conquer）」實現，即將大問題拆成多個小問題，一一處理小問題後，就能解決大問題。
圖示
以下可用圖示理解「merge sort」如何以「divide and conquer」方式，將原陣列 [5,4,6,9,8,1,3,2] 由小到大排列。
上半部的「divide」將陣列的長度從 8 縮減為 1，再一一比較每個小陣列中值的大小，並進行排列。
下半部「conquer」排序過程
在陣列長度為 1 時，這八個陣列都已經排序好：
將已經排序好、長度為 1 的陣列兩兩比較，數值較小者先取，組合成已經排序好、長度為 2 的陣列：
排序好長度為 2 的陣列如下：
接著將已經排序好、長度為 2 的陣列兩兩比較，數值小者先取，組合成已經排序好、長度為 4 的陣列：
排序好長度為 4 的陣列如下：
最後將已經排序好、長度為 4 的陣列兩兩比較，數值小者先取，組合成已經排序好、長度為 8 的陣列：
整個陣列最終排序結果如下：
偽代碼&說明
「合併排序」的程式碼分為兩個部分，包含 MERGE() 將兩個已排序的小陣列合併成排序好的大陣列，還有 MERGE-SORT() 實現「分而治之」。
下列偽代碼及程式碼皆以「將陣列由小到大排序」為目標：
第一部分：MERGE()
輸入兩個已經排序好的小陣列「arr1」與「arr2」，透過指標「i」與「j」逐一比較兩陣列中的值，較小者優先放入新建的空陣列「result」。
若其中一陣列全部比較完後，另一陣列仍有未放入「result」的值，因為小陣列的資料都已經排序過，可以直接把小陣列中剩下的值直接搬運到「result」當中。
第二部分：MERGE-SORT()
先取陣列中間值「middle」，接著用「slice()」將陣列分為左右兩邊，直到陣列長度為 1 為止；接著透過遞迴搭配「MERGE()」函數，將小陣列不斷合併、排序，直到輸入的「arr」每筆資料都被排序過為止。
合併排序透過兩個小陣列各自的指標逐一比較、排序，同樣大小的值會按照原順序排在最終結果中，屬於「穩定排序（stable sort）」。
程式碼範例（JavaScript）
//第一部分
function merge(arr1, arr2){
//製作空陣列result&指標i、j
let result = [];
let i = 0;
let j = 0;
//將兩陣列合併，並由小到大一一放進result
while(i < arr1.length && j < arr2.length){
if(arr1[i] < arr2[j]){
result.push(arr1[i]);
i++;
} else {
result.push(arr2[j]);
j++;
}
}
//若arr2比arr1先清空，則將arr1剩下的資料直接搬到result
while(i < arr1.length){
result.push(arr1[i]);
i++;
}
//若arr1比arr2先清空，則將arr2剩下的資料直接搬到result
while(j < arr2.length){
result.push(arr2[j]);
j++;
}
return result;
}
//第二部分
function mergeSort(arr){
//遞迴終止條件：arr長度被切為1時
if(arr.length === 1){
return arr;
} else {
//透過遞迴，先將arr不斷分兩半，再用MERGE()將切小的陣列不斷合併、排序
//用slice把陣列切兩半，slice括弧內的開始處有包含、結束處不包含
let middle = Math.floor(arr.length / 2);
let left = arr.slice(0, middle); //做一個0到middle-1的小陣列
let right = arr.slice(middle,arr.length); //做一個middle到arr.length的小陣列
//用遞迴實現「分而治之」
return merge(mergeSort(left), mergeSort(right));
/*
1. 首先執行括號內的mergeSort：
左半邊小陣列跟右半邊小陣列都持續對半切，直到所有陣列長度變成1為止，就會到上面的if條件判斷區，回傳arr
2. mergeSort全部跑完後，接著執行外面的merge：
將陣列一一用merge比較、合併，持續回傳已經排序好的小陣列，直到整個陣列都被merge為止
*/
}
}時間複雜度
不論最差、最佳或平均情況，皆為 O(n·log n)。
現假設原陣列長度為 n，在逐次分割至長度為 1 的陣列之過程中，每分割一次長度都減半，圖示如下：
由上圖可觀察「分割次數」與「陣列長度」之關係，結果如下表，表中最右方以對數形式呈現的「分割次數」相等於最左方以正整數形式呈現「分割次數」的值：
由右方綠色表格最下方的結論可知：若要將原長度為 n 的陣列切到長度剩下 1，共需要分割 (log₂ n) 次，過程中的每層又有 n 筆資料要處理，因此分割過程的時間複雜度為 O(n·log₂ n)。
同樣地，從長度為 1 的陣列合併回長度為 n 的陣列也會有 (log₂ n) 層，而在每層的小陣列中，這 n 筆資料全都要排序、比較一次，因此合併過程的時間複雜度也是 O(n·log₂ n)。
分割的時間複雜度為 O(n·log₂ n)、合併的時間複雜度同為 O(n·log₂ n)，因此總時間複雜度為 O(2n·log₂ n)=O(n·log n)。
空間複雜度
O(n)：由於合併排序非屬「原地演算法（in-place algorithm）」，在分割及合併的過程中，需額外 O(n) 的空間儲存小陣列，遞迴過程另需要 O(log n)，兩者加總取較大者：O(n)+O(log n)=O(n)。