合併排序是一種基於分治法的高效排序演算法。其核心思想是將陣列遞迴拆分為單一元素的子陣列,再將有序的子陣列兩兩合併,最終得到完整有序序列。時間複雜度穩定為 O(n log n),且屬於穩定排序。
此版本使用 slice 與 concat 簡化陣列操作,程式碼精簡易讀:
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));
}
}
// 測試
var arr = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];
mergeSort(arr);
console.log(arr); // [1, 2, 3, 5, 12, 15, 23, 32, 66, 87]
此版本模擬底層陣列操作,並記錄每一趟排序結果,方便觀察合併過程:
var count = 0;
function mSort(source, dest, s, t) {
var result = "";
var m;
var dest2 = [];
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);
// 輸出每趟結果
result += "<br />第" + ++count + "遍排序的結果是:";
for (var n = 0; n < dest.length; n++) {
result += dest[n] + ",";
}
}
return result;
}
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];
}
}
// 使用範例
var array = [12, 25, 32, 16, 18, 27, 59, 69, 36];
var dest = [];
mSort(array, dest, 0, array.length - 1);
console.log("最終結果:", dest);
| 特性 | 範例一 | 範例二 |
|---|---|---|
| 程式碼簡潔度 | 高 | 中 |
| 記憶體額外開銷 | 較大(頻繁建立新陣列) | 較小(原地操作) |
| 適合場景 | 一般應用、快速開發 | 教學演示、記憶體受限環境 |
合併排序以穩定的 O(n log n) 表現,是處理大量資料排序的首選演算法之一。理解其分治與合併機制,有助於掌握更多進階演算法的設計思想。