python - 什么时候会使用递归合并排序而不是迭代？

Question

是否存在应该使用递归合并排序而不是迭代合并排序的情况？最初，我认为合并排序的迭代方法通常更快，尽管我无法在自己的实现中证明这一点。但是递归会对堆栈进行更多的调用，这反过来又降低了内存效率。如果我有一个非常大的数据集需要排序怎么办？那么使用递归不是很糟糕吗？因为过度深度的递归最终不会导致堆栈溢出吗？如果递归速度较慢且内存效率较低，为什么还要使用递归而不是迭代？

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    current_size = 1
    while current_size < len(arr):
        left = 0
        while left < len(arr)-1:
            mid = left + current_size - 1
            right = min((left + 2*current_size - 1), (len(arr)-1))
            merged_arr = merge(arr[left : mid + 1], arr[mid + 1 : right + 1])
            for i in range(left, right + 1):
                arr[i] = merged_arr[i - left]
            left = left + current_size*2
        current_size = current_size * 2
    return arr

def merge(left, right):
    result = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

def merge_sort_recursive(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    left = merge_sort_recursive(left)
    right = merge_sort_recursive(right)
    return merge(left, right)

def merge(left, right):
    result = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

Answer 1

更新 嗯，在编写了我自己的更简单的迭代之后，我必须收回我写的一些内容......

def merge_sort_Kelly(arr):
    half = 1
    while half < len(arr):
        for mid in range(half, len(arr), 2*half):
            start = mid - half
            stop = mid + half
            arr[start:stop] = merge(arr[start:mid], arr[mid:stop])
        half *= 2
    return arr

对三个洗牌排序的时间list(range(2**17)) (Try it online!):

1.35 seconds merge_sort
0.91 seconds merge_sort_recursive
0.90 seconds merge_sort_Kelly

1.25 seconds merge_sort
1.05 seconds merge_sort_recursive
0.92 seconds merge_sort_Kelly

1.34 seconds merge_sort
0.81 seconds merge_sort_recursive
0.88 seconds merge_sort_Kelly

它几乎和递归一样快，而且我想说几乎和递归一样简单。甚至是 end 的边界检查毕竟是不必要的，因为 Python 切片为我处理了这个问题。不平衡问题依然存在。

关于内存效率:实际上，您的迭代比递归占用更多内存，而不是更少。以下是 list(range(2**17)) 排序期间的分配峰值用 tracemalloc 测量(Try it online!):

3,342,704 bytes  merge_sort
2,892,479 bytes  merge_sort_recursive
2,752,720 bytes  merge_sort_Kelly
  525,572 bytes  merge_sort_Kelly2 (see text below)

在最终/顶级合并期间达到峰值。您的迭代需要更多时间，因为在计算最终的 merged_arr 时，该变量仍然保留前一个变量。可以通过 del merged_arr 来避免当不再需要它时。那么只需要 2,752,832 字节。当然，如果我们不制作这么多切片副本而是使用索引，那么我们所有的解决方案都可以占用更少的内存。这就是merge_sort_Kelly2做。它只复制其合并函数，并且只复制一半，然后将原始列表中的一半和另一半合并到原始列表中。

更新结束，原始答案:

Why would you ever use recursive over iterative

主要是因为它更简单/更好。例如，您的递归可以对 [3, 1, 4] 进行排序而您的迭代崩溃并显示 IndexError 。毫无疑问，因为它更复杂。

递归也更加平衡，需要更少的比较。左侧和右侧始终相等或仅相差一个元素。例如，对于 arr = list(range(2**17)) ，两者都进行了 1114112 次比较，因为两者同样完美平衡。但随着2**17+1 ，迭代进行了 1245184 次比较，而递归则只进行了 1114113 次比较。因为迭代最后将 2^17 个元素与 1 个元素合并(并且该元素恰好是最大的)。

I timed these two implementations and found iterative does in fact appear to be faster.

我的看法恰恰相反。即使对于 2^17 个元素，迭代也不会出现不平衡问题。对三个列表进行双向排序所需的时间:

1.23 seconds merge_sort
0.83 seconds merge_sort_recursive

1.25 seconds merge_sort
0.82 seconds merge_sort_recursive

1.19 seconds merge_sort
0.80 seconds merge_sort_recursive

代码:

from random import shuffle
from time import time

for _ in range(3):
    arr = list(range(2**17))
    shuffle(arr)
    for sort in merge_sort, merge_sort_recursive:
        copy = arr[:]
        t0 = time()
        copy = sort(copy)
        print(f'{time()-t0:.2f} seconds {sort.__name__}')
        assert copy == sorted(arr)
    print()