python - 替代合并排序的效率？

Question

我正在学习合并排序，我看过的许多教程都是通过替换原始数组的值来合并的，例如 here 的方式.我想知道我的替代实现是否正确。我只看到 1 tutorial照着做。我的实现返回排序后的数组，如下所示:

def mergesort(arr):
    if len(arr) == 1:
        return arr
    mid = len(arr) // 2
    left_arr = arr[:mid]
    right_arr = arr[mid:]

    return merge(mergesort(left_arr), mergesort(right_arr))

def merge(left_arr, right_arr):
    merged_arr = [] # put merge of left_arr & right_arr here
    i,j = 0, 0 # indices for left_arr & right_arr

    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] < right_arr[j]:
            merged_arr.append(left_arr[i])
            i += 1
        else:
            merged_arr.append(right_arr[j])
            j += 1

    # add remaining elements to resulting arrray
    merged_arr.extend(left_arr[i:]) 
    merged_arr.extend(right_arr[j:])
    return merged_arr


arr = [12, 11, 13, 5, 6, 7]
sorted_arr = mergesort(arr)
print(sorted_arr)
# Output: [5, 6, 7, 11, 12, 13]

对我来说，这是一种更直观的归并排序方式。这个实现是否打破了合并排序应该是什么？它在速度方面或空间方面的效率是否较低(除了创建结果数组)？

Answer 1

如果我们正在考虑使用 O(n) 额外内存的合并排序，那么您的实现似乎是正确的但效率低下。让我们看看这些行:

def mergesort(arr):
    ...
    mid = len(arr) // 2
    left_arr = arr[:mid]
    right_arr = arr[mid:]

您实际上是在每次调用 mergesort() 时创建两个新数组，然后从原始 arr 复制元素。它是堆上的两个额外内存分配和 O(n) 副本。通常，由于复杂的分配器算法，堆内存分配非常慢。

老爸，让我们考虑一下这条线:

merged_arr.append(left_arr[i])  # or similar merged_arr.append(left_arr[j])

这里又发生了一堆内存分配，因为您使用了动态分配的数组(又名列表)。

因此，合并排序最有效的方法是在一开始就分配一个与原始数组大小相同的额外数组，然后将其部分用于临时结果。

def mergesort(arr):
    mergesort_helper(arr[:], arr, 0, len(arr))

def mergesort_helper(arr, aux, l, r):
    """ sorts from arr to aux """
    if l >= r - 1:
        return

    m = l + (r - l) // 2
    mergesort_helper(aux, arr, l, m)
    mergesort_helper(aux, arr, m, r)
    merge(arr, aux, l, m, r)

def merge(arr, aux, l, m, r):
    i = l
    j = m
    k = l
    while i < m and j < r:
        if arr[i] < arr[j]:
            aux[k] = arr[i]
            i += 1
        else:
            aux[k] = arr[j]
            j += 1
        k += 1

    while i < m:
        aux[k] = arr[i]
        i += 1
        k += 1

    while j < r:
        aux[k] = arr[j]
        j += 1
        k += 1

import random

def testit():
    for _ in range(1000):
        n = random.randint(1, 1000)
        arr = [0]*n
        for i in range(n):
            arr[i] = random.randint(0, 100)

        sarr = sorted(arr)
        mergesort(arr)
        assert sarr == arr

testit()