自底向上归并排序：不用递归的迭代版
先合并长度为 1 的有序段，再 2、4、8… 段长翻倍，趟数 ⌈log₂n⌉，免递归栈。
自底向上版不用递归，直接从长度为 1 的有序段开始，两两合并，段长不断翻倍。
图：迭代版归并——段长 1→2→4→… 两两合并
def merge_sort_bottom_up(arr):
n = len(arr)
width = 1
while width < n:
for lo in range(0, n, 2*width):
mid = min(lo+width, n)
hi = min(lo+2*width, n)
arr[lo:hi] = merge(arr[lo:mid], arr[mid:hi])
width *= 2
return arr
趟数 = ⌈log₂n⌉，每趟处理全部 n 个元素，总复杂度仍 Θ(n log n)，且避免递归栈，空间更可控。
相关推荐：插入排序（也是迭代） · 分治思想
评论 (0)
正文划词可点「问萝卜特」——自动发评论并由 AI 回复
加载评论中…