分治法三步驟:
def merge(arr, left, mid, right)
left_arr = arr[left..mid]
right_arr = arr[mid+1..right]
# 哨兵值避免邊界檢查
left_arr << Float::INFINITY
right_arr << Float::INFINITY
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
# 測試
arr = Array.new(13) { rand(100) }
puts "Original: #{arr}"
merge_sort(arr, 0, arr.size-1)
puts "Sorted: #{arr}"
# Original: [4, 32, 84, 58, 49, 40, 75, 29, 82, 21, 70, 37, 70]
# Sorted: [4, 21, 29, 32, 37, 40, 49, 58, 70, 70, 75, 82, 84]
在兩子陣列末尾加入 Float::INFINITY,合併迴圈無需檢查 i < left_arr.size 等邊界條件,簡化邏輯並提升速度。
| 指標 | 合併排序 | 快速排序 | 堆積排序 |
|---|---|---|---|
| 時間 (平均) | O(n log n) | O(n log n) | O(n log n) |
| 時間 (最壞) | O(n log n) | O(n²) | O(n log n) |
| 空間 | O(n) 輔助陣列 | O(log n) 堆疊 | O(1) 原地 |
| 穩定性 | 穩定 | 不穩定 | 不穩定 |
def merge_sort_func(a)
return a if a.size <= 1
mid = a.size / 2
left = merge_sort_func(a[0...mid])
right = merge_sort_func(a[mid..-1])
merge_func(left, right)
end
def merge_func(l, r)
res = []
while l.any? && r.any?
res << (l.first <= r.first ? l.shift : r.shift)
end
res + l + r
end
Array#sort (C 實作 Timsort,混合合併+插入,極快且穩定)。arr.sort { |a,b| a.length <=> b.length } 或 arr.sort_by(&:length)。