为什么归并排序性能是线性的 [Python]

Question

我正在研究比较 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

任何建议或解释将不胜感激！

Answer 1

我认为你的 mergeSort 函数有一个错误。您为左右子数组创建了 NumPy 数组。在我看来，这是额外且不必要的步骤。

试试这个

def mergeSort(A, p, q, r): n1 = q - p + 1 n2 = r - q

L = A[p:p + n1]
R = A[q + 1:q + 1 + n2]

i = j = 0
k = p  

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

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

while j < n2:
    A[k] = R[j]
    j += 1
    k += 1