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

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

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

\n

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

\n

三个随机排序的时间list(range(2**17))（在线尝试！）：

\n

1.35 seconds merge_sort\n0.91 seconds merge_sort_recursive\n0.90 seconds merge_sort_Kelly\n\n1.25 seconds merge_sort\n1.05 seconds merge_sort_recursive\n0.92 seconds merge_sort_Kelly\n\n1.34 seconds merge_sort\n0.81 seconds merge_sort_recursive\n0.88 seconds merge_sort_Kelly\n

\n

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

\n

关于内存效率：实际上，您的迭代比递归需要更多的内存，而不是更少。以下是排序期间的分配峰值list(range(2**17))（tracemalloc在线尝试！）：

\n

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

\n

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

\n

更新结束，原答案：

\n

\n

为什么你会使用递归而不是迭代

\n

\n

主要是因为它更简单/更好。例如，您的递归程序可以排序[3, 1, 4]，而您的迭代程序则因IndexError. 毫无疑问，因为它更复杂。

\n

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

\n

\n

我对这两个实现进行了计时，发现迭代实际上似乎更快。

\n

\n

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

\n

1.23 seconds merge_sort\n0.83 seconds merge_sort_recursive\n\n1.25 seconds merge_sort\n0.82 seconds merge_sort_recursive\n\n1.19 seconds merge_sort\n0.80 seconds merge_sort_recursive\n

\n

代码：

\n

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

\n