Ruby 實現合併排序演算法：分治法遞歸實作與哨兵優化

合併排序是穩定、O(n log n) 最壞情況保證的排序演算法。本文提供 Ruby 實作，採用分治法遞歸分解、哨兵值簡化合併邊界判斷、原地合併最小化額外空間。

完整程式碼

# encoding: utf-8
MAX = 100  # 哨兵值，大於所有可能輸入

# 產生測試資料
array = Array.new(13) { rand(100) }
puts "The original array is: #{array}"

def merge(arr, left, mid, right)
  # 建立左右子陣列 + 哨兵
  left_arr = arr[left..mid] + [MAX]
  right_arr = arr[mid+1..right] + [MAX]

  i = j = 0
  (left..right).each do |k|
    if left_arr[i] <= right_arr[j]
      arr[k] = left_arr[i]
      i += 1
    else
      arr[k] = right_arr[j]
      j += 1
    end
  end
end

def merge_sort(arr, left, right)
  return if left >= right
  mid = (left + right) / 2
  merge_sort(arr, left, mid)
  merge_sort(arr, mid+1, right)
  merge(arr, left, mid, right)
end

merge_sort(array, 0, array.size-1)
puts "The sorted array is: #{array}"

執行輸出範例

The original array is: [4, 32, 84, 58, 49, 40, 75, 29, 82, 21, 70, 37, 70]
The sorted array is: [4, 21, 29, 32, 37, 40, 49, 58, 70, 70, 75, 82, 84]

關鍵技術點

哨兵優化

• 在左右子陣列末尾加入 MAX (大於所有輸入值)
• 合併迴圈無需檢查陣列邊界，left_arr[i] <= right_arr[j] 自然處理耗盡情況
• 減少分支預測失敗，提升效能

原地合併

• 直接在原陣列 arr[left..right] 寫入結果
• 額外空間：O(n) 用於左右子陣列複製 (可優化為單一暫存陣列)

遞歸分解

• merge_sort(arr, left, right) 處理半開區間 [left, right]
• 基底情況 left >= right (單元素或空)

複雜度分析

Ruby 風格替代寫法（函數式、非原地）

def merge_sort_func(arr)
  return arr if arr.size <= 1
  mid = arr.size / 2
  left = merge_sort_func(arr[0...mid])
  right = merge_sort_func(arr[mid..-1])
  merge_func(left, right)
end

def merge_func(left, right)
  result = []
  until left.empty? || right.empty?
    result << (left.first <= right.first ? left.shift : right.shift)
  end
  result + left + right
end

# 使用
p merge_sort_func([4, 32, 84, 58, 49, 40, 75, 29, 82, 21, 70, 37, 70])

總結

本實作展示教科書級合併排序：分治遞歸、哨兵簡化合併邏輯、原地排序。Ruby 區間語法 arr[left..mid] 使子陣列切片極為直觀。生產環境建議使用內建 Array#sort (Timsort)，但理解合併排序機制對掌握分治法、外部排序、平行排序至關重要。