合并插入混合排序中的关键比较

Question

我得到的任务是合并插入排序描述为（解释）：

Starting off with merge sort, once a threshold S(small positive integer) is reached, the algorithm will then sort the sub arrays with insertion sort.

我们的任务是为不同长度的输入找到最佳 S 值，以实现 最少的密钥比较 。我通过修改在线可用的内容来实现代码以获得：

def mergeSort(arr, l, r, cutoff):
    if l < r:
        m = l+(r-l)//2
        if len(arr[l:r+1]) > cutoff:            
            return mergeSort(arr, l, m, cutoff)+mergeSort(arr, m+1, r, cutoff)+merge(arr, l, m, r)

        else:
            return insertionSort(arr, l, r+1)
    
    return 0

def merge(arr, l, m, r):
    comp = 0
    n1 = m - l + 1
    n2 = r - m

    L = [0] * (n1)
    R = [0] * (n2)

    for i in range(0, n1):
        L[i] = arr[l + i]

    for j in range(0, n2):
        R[j] = arr[m + 1 + j]

    i = 0
    j = 0
    k = l

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
        comp +=1

    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1
    
    return comp

def insertionSort(arr, l, r):
    comp = 0
    for i in range(l+1, r):
 
        key = arr[i]
 
        j = i-1
        while j >= l:
            if key >= arr[j]:
                comp += 1
                break
            arr[j + 1] = arr[j]
            j -= 1
            comp += 1
        arr[j + 1] = key

    return comp

然而，我得到的 S 的最小值与长度的关系图是：

这意味着近乎纯粹的合并排序几乎总是优于混合排序。这与在线可用的内容相反，它说插入排序在低 S（~10-25）值时比合并排序执行得更快。我的代码似乎找不到任何错误，所以混合排序真的比合并排序好吗？

Answer 1

IMO 这个问题有问题。

Mergesort 总是执行 N Lg(N) 次键比较，而 Insertionsort 执行其中的 N²/2 次。因此，从 N=2 开始，比较计数在所有情况下都支持 Mergesort。（这只是近似值，因为 N 并不总是均分）。

但是移动次数和开销将倾向于有利于插入排序。因此，更相关的指标是实际运行时间，不幸的是，这将取决于密钥长度和类型。

合并插入混合排序中的关键比较

Key comparisons in a merge-insertion hybrid sort

python

sorting

algorithm

merge