← 返回首頁

🔀 合併排序法

Merge Sort - 可視化演示與詳細解釋

什麼是合併排序法？

合併排序是一種分治型排序演算法，通過遞迴地將陣列分成更小的子陣列，分別排序，然後將排序好的子陣列合併回去。

演算法特點

  • 分治策略：採用分治法，遞迴分解和合併
  • 穩定排序：相等元素的相對位置不改變
  • 高效性：時間複雜度穩定為O(n log n)
  • 額外空間：需要O(n)的額外空間用於合併

排序原理

將陣列不斷二分，直到每個部分只有一個元素，然後將相鄰的部分有序地合併，最終得到完全排序的陣列。

互動演示

比較次數：0

合併次數：0

當前步驟：就緒

時間與空間複雜度

情景 時間複雜度 說明
最好情況 O(n log n) 任何情況下都需要進行分割和合併
平均情況 O(n log n) 穩定的效能表現
最壞情況 O(n log n) 性能保證，不隨數據變化
空間複雜度 O(n) 合併過程需要額外的暫存空間

詳細步驟

  1. 將陣列從中點分成兩個子陣列
  2. 遞迴地對左子陣列執行合併排序
  3. 遞迴地對右子陣列執行合併排序
  4. 遞迴的基本情況：子陣列只有一個元素時停止
  5. 將兩個已排序的子陣列合併成一個排序的陣列
  6. 比較兩個子陣列的首元素，將較小的加入結果
  7. 重複步驟 6 直到其中一個子陣列為空
  8. 將剩餘元素加入結果陣列

虛擬碼與實際程式碼對照

這裡顯示 Merge Sort 的分治邏輯，將虛擬碼與 JavaScript 的遞迴與合併步驟對照。

虛擬碼

function mergeSort(arr):
    if length(arr) <= 1:
        return arr
    mid = length(arr) / 2
    left = mergeSort(arr[0:mid])
    right = mergeSort(arr[mid:])
    return merge(left, right)

function merge(left, right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    return result + left + right

JavaScript 對照

async function mergeSort(left = 0, right = array.length - 1, sortedIndices = []) {
    if (!isSorting) return;
    if (left >= right) return;
    const mid = Math.floor((left + right) / 2);
    await mergeSort(left, mid, sortedIndices);
    await mergeSort(mid + 1, right, sortedIndices);
    await merge(left, mid, right, sortedIndices);
}

async function merge(left, mid, right, sortedIndices) {
    const leftArray = array.slice(left, mid + 1);
    const rightArray = array.slice(mid + 1, right + 1);
    // 合併邏輯與比較行為
}

程式碼與動畫對應

if (left >= right) return;                 -> 遞迴基底，當子區段長度為 0 或 1 時停止，不做動畫
const mid = Math.floor((left + right) / 2);   -> 計算分割點，動畫將資料分成左右兩部分
await mergeSort(left, mid,...);               -> 遞迴排序左半部分，動畫依序呈現左側子問題
await mergeSort(mid + 1, right,...);         -> 遞迴排序右半部分，動畫呈現右側子問題
await merge(left, mid, right,...);           -> 合併排序步驟，開始比較與放置元素動畫
const leftArray = array.slice(...);           -> 建立左右暫存子陣列，用於合併過程的動畫比較
// 合併邏輯與比較行為                   -> 在合併循環中，高亮比較的兩個元素並依結果放入排序位置

邊界條件（Boundary Conditions）