視覺化展示
左右比較中
合併並寫回陣列
░░░ 非當前處理區間 (變暗)
400ms
演算法偽代碼
function mergeSort(arr, start, end):
1 if start >= end: return
2 mid = floor((start + end) / 2)
3 mergeSort(arr, start, mid) // 分割左半邊
4 mergeSort(arr, mid + 1, end) // 分割右半邊
5 merge(arr, start, mid, end) // 將兩邊合併
function merge(arr, start, mid, end):
6 while left <= mid and right <= end:
7 if arr[left] <= arr[right]: // 比較兩邊最小元素
8 temp.push(arr[left])
9 else:
10 temp.push(arr[right])
11 // ...將剩餘元素放入 temp 陣列中...
12 for k = 0 to temp.length - 1:
13 arr[start + k] = temp[k] // 將排好序的 temp 寫回原陣列
操作原理
合併排序法是一種高效的、基於分治法 (Divide and Conquer) 的排序演算法。它將一個大問題分解成數個小問題來解決，然後再將小問題的解合併起來，得到原問題的解。
這個演算法的核心思想是「先分割，後合併」。它能保證穩定的排序結果，且時間複雜度表現優秀。
操作過程
- 分割 (Divide): 將目前的陣列遞迴地對半分割，直到每個子陣列只剩下一個元素。只包含一個元素的陣列被視為已排序。
- 合併 (Conquer/Merge): 從最小的子陣列開始，兩兩成對地進行合併。在合併過程中，比較兩個子陣列的元素，並按照順序將它們放入一個新的臨時陣列中。
- 重複合併步驟，直到所有子陣列都被合併回一個完整的、已排序的陣列。
複雜度分析
- 時間複雜度 (所有情況):
O(n log n)
無論是最好、最壞還是平均情況，合併排序法的時間複雜度都非常穩定。分割過程需要 log n 層，每層的合併操作總共需要 O(n) 的時間。 - 空間複雜度 (Space Complexity):
O(n)
合併操作需要一個與原陣列等大的臨時陣列來存放合併後的結果，因此空間複雜度為 O(n)。