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()