合併排序法是一種高效的排序演算法，採用分治法的思想。它將待排序的資料列逐次分割成較小的部分，對各部分進行排序，最後將各部分合併成一個有序的序列。
| 項目 | 複雜度 | 說明 |
|---|---|---|
| 最壞時間複雜度 | O(n log n) | 任意情況下都是這個複雜度 |
| 平均時間複雜度 | O(n log n) | 隨機排序的情況 |
| 最佳時間複雜度 | O(n log n) | 陣列已排序時仍為 O(n log n) |
| 空間複雜度 | O(n) | 需要額外的空間儲存臨時子陣列 |
function mergeSort(arr) {
if (arr.length <= 1) return arr;
// 分割
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
// 合併
return merge(left, right);
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}