🧠 合併排序法演示

操作原理

  1. 使用分治法，把陣列不斷切成左右兩半。
  2. 每一半再繼續切分，直到子陣列長度為 1。
  3. 將相鄰的兩個已排序子陣列合併成更大的已排序陣列。
  4. 重複合併，最後得到完整排序結果。

操作過程步驟

  1. 呼叫 mergeSort(left, right)。
  2. 若 left >= right，代表區間只剩一個元素，直接返回。
  3. 計算 mid，把區間切成 [left..mid] 與 [mid+1..right]。
  4. 遞迴排序左右區間。
  5. 比較左右兩側目前元素，較小者放進暫存陣列。
  6. 把暫存結果寫回原陣列，完成該區間排序。

時間複雜度分析

最壞情況：O(n log n)
每層合併要掃過 n 個元素，總共有 log n 層
平均情況：O(n log n)
分割與合併結構固定，平均效率也維持在 n log n
最佳情況：O(n log n)
即使資料接近有序，仍要進行完整分割與合併流程
空間複雜度：O(n)
需要額外暫存陣列來進行合併

視覺化演示

按下「開始排序」觀察分割與合併寫回的過程
目前合併區間
左半比較指標
右半比較指標
寫回位置
排序完成
比較次數: 0
寫回次數: 0