python 中合并排序、插入排序和递归插入排序的运行时比较

Question

def merge_sort(unorderedList):
    if len(unorderedList) > 1:
        mid = len(unorderedList) // 2 
        left = unorderedList[:mid]
        right = unorderedList[mid:]
        merge_sort(left)
        merge_sort(right)
        i = 0
        j = 0
        k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                unorderedList[k] = left[i]
                i += 1
            else:
                unorderedList[k] = right[j]
                j += 1
            k += 1
        while i < len(left):
            unorderedList[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            unorderedList[k] = right[j]
            j += 1
            k += 1

def insertion_sort(list1):
    for i in range(1, len(list1)):
        key = list1[i]
        j = i - 1 
        while j >= 0 and list1[j] > key:
            list1[j + 1] = list1[j]
            j -= 1
        list1[j + 1] = key

def recursive_insertion_sort(arr, n):
    if n <= 1:
        return

    recursive_insertion_sort(arr, n-1)
    last = arr[n-1]
    j = n-2
     
    while j >= 0 and arr[j] > last:
        arr[j + 1] = arr[j]
        j -= 1
 
    arr[j + 1] = last

import time
import random
t0 = time.time()
insertion_sort([random.randint(-10000, 10000) for i in range(50000)])
t1 = time.time()
recursive_insertion_sort([random.randint(-10000, 10000) for i in range(50000)])
t2 = time.time()
merge_sort([random.randint(-10000, 10000) for i in range(50000)])
t3 = time.time()

print("insertion sort timer : ", t1 - t0)
print("recursive insertion sort timer : ", t2 - t1)
print("merge sort timer : ", t3 - t2)

我使用这三个函数来比较它们在 5 万成员随机列表上的运行时间
我在 vscode

中用 python 3.10 得到了这些时间

插入排序计时器：78.13s
递归插入排序定时器：0.068s
合并排序计时器：0.209s
这个对吗？如果是这样，你能解释一下吗？
考虑到合并排序的顺序为 O(nlogn)，而插入排序的顺序为 O(n^2)，这是怎么发生的？

编辑：添加了用于时间测试的代码和方法。

Answer 1

由于这些函数执行的是“就地”排序，我怀疑您的指标不是从同一个原始列表开始的。

例如，如果您先在列表 A 上测试 merge_sort，然后在 A 上测试 insertion_sort，则第二次排序会得到一个已排序的列表，该列表使用该算法应该从中受益。这可能是“插入排序”测量和“递归插入排序”测量之间发生的情况。

理论上，recursive_insertion_sort 函数不应该能够对超过 990 个项目的任何列表进行排序。所以，我猜你更改了最大递归深度限制（如果你没有更改，那么实验中还有其他问题）

如果您独立测试每个排序（或在原始列表的副本上），您应该会得到截然不同的结果。

python 中合并排序、插入排序和递归插入排序的运行时比较

Runtime comparison between merge sort, insertion sort and recursive insertion sort in python

python

sorting

time-complexity

编辑：添加了用于时间测试的代码和方法。