合併排序是建立在「合併」操作上的排序法,也是分治法最典型的應用:先把序列切成子序列讓各自有序,再把有序的子序列逐層合併成完整的有序序列。若只合併兩個有序表,稱為二路合併。
取中點切成左右兩半,各自遞迴排序後合併,再用 splice 把結果寫回原陣列,因此函式會回傳同一個陣列參考:
function mergeSort(items) {
if (items.length < 2) { return items; }
var middle = Math.floor(items.length / 2),
left = items.slice(0, middle),
right = items.slice(middle),
params = merge(mergeSort(left), mergeSort(right));
params.unshift(0, items.length);
items.splice.apply(items, params);
return items;
function merge(left, right) {
var result = [], il = 0, ir = 0;
while (il < left.length && ir < right.length) {
if (left[il] < right[ir]) { result.push(left[il++]); }
else { result.push(right[ir++]); }
}
return result.concat(left.slice(il)).concat(right.slice(ir));
}
}
mergeSort([2, 1, 3, 12, 5, 66, 23, 87, 15, 32]);
另一種常見寫法是把 source 與 dest 拆開,先遞迴排到暫存陣列,再由 merge 把兩段有序區間併回目標陣列,並在過程中輸出每一輪的排序結果,方便觀察合併的進行方式:
function mSort(source, dest, s, t) {
var m, dest2 = new Array();
if (s == t) { dest[s] = source[s]; }
else {
m = Math.floor((s + t) / 2);
mSort(source, dest2, s, m);
mSort(source, dest2, m + 1, t);
merge(dest2, dest, s, m, t);
}
return dest;
}
function merge(source, dest, s, m, n) {
for (var j = m + 1, k = s; j <= n && s <= m; k++) {
if (source[s] < source[j]) { dest[k] = source[s++]; }
else { dest[k] = source[j++]; }
}
if (s <= m) { for (var l = 0; l <= m - s; l++) { dest[k + l] = source[s + l]; } }
if (j <= n) { for (var l = 0; l <= n - j; l++) { dest[k + l] = source[j + l]; } }
}
合併排序的時間複雜度穩定為 O(n log n),且是常見排序法中少數具穩定性的;代價是需要 O(n) 的額外空間。若資料量不大,實務上常會在子陣列小到一定程度時改用插入排序,以减少遞迴與配置成本。