归并排序（Merge Sort）性能呈线性？Python排序算法测试异常求助

我正在Python中对比各类排序算法，已经实现了算法和测试函数，能针对不同输入规模（最高到数十万级）评估算法性能，执行时间会保存下来用于后续绘图。如预期，选择排序呈现二次复杂度，对应的图像符合该特征，但归并排序的图像却呈现线性特征，和预期的nlogn复杂度不符！

归并排序实现代码 #

def merge_sort(A):
    merge_sort_aux(A, 0, len(A) - 1)

# Merge Sort Helper Function
# (Recursive)
def merge_sort_aux(A, p, r):
    if p < r:
        q = (p + r) // 2  # Integer division
        merge_sort_aux(A, p, q)
        merge_sort_aux(A, q + 1, r)
        merge(A, p, q, r)

def merge(A, p, q, r):
    # Calculate the sizes of the two sublists
    n1 = q - p + 1
    n2 = r - q

    # Create two NumPy arrays initially initialized to 0 
    # They are of type float to support sentinels
    L = np.zeros(n1 + 1, dtype=float)
    R = np.zeros(n2 + 1, dtype=float)

    # Copy data into NumPy arrays
    L[:n1] = [A[p + i] for i in range(n1)]
    R[:n2] = [A[q + 1 + j] for j in range(n2)]

    # Sentinels
    L[n1] = np.inf
    R[n2] = np.inf

    i = j = 0

    for k in range(p, r + 1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1  # Increment the index of the left sublist to preserve the loop invariant
        else:
            A[k] = R[j]
            j += 1  # Increment the index of the right sublist

测试函数代码 #

def test_algo(algo_function, maxRange=TEST_MAX_DIMENSION, minRange=2, step=TEST_STEP):
    """
    Test the execution time of the given algorithm function for various input sizes.

    Parameters:
    - algo_function: The algorithm function to be tested.
    - maxRange: The maximum input size to be tested.
    - minRange: The minimum input size to start the testing.
    - step: The step size between different input sizes.

    Returns:
    - results: A dictionary to store the execution times for each input size.
    """

    results = {}  # Dictionary to store execution times for each input size

    for i in range(minRange, maxRange, step):
        A = random_list(i)  # Assuming you have a function 'random_list' generating a list of size i
        start = timer()
        algo_function(A)
        end = timer()
        results[i] = end - start

    return results

性能图像 #

• 归并排序性能图：
• 300万元素规模测试图：

恳请各位提供排查建议或解释！

内容的提问来源于stack exchange，提问作者Niccolò Caselli