Mergesort vs nlogn曲线（Python）（未获得预期图）

Question

我正在尝试在对N元素与NLOGN进行排序的合并排序的执行时间之间绘制图形，但是我没有得到预期的图形。

from random import randint
from math import log2
import timeit
import matplotlib.pyplot as plt


def merge(arr, l, m, r):
    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    # Initial index of first subarray
    j = 0    # Initial index of second subarray
    k = l    # Initial index of merged subarray

    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

    # Copy the remaining elements
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    # Copy the remaining elements
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1


def mergeSort(arr, l, r):
    if l < r:
        m = l+(r-l)//2
        mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)


arr = []
x = []
y = []
n = []
for i in range(1, 3000, 100):
    for j in range(i):
        temp = randint(0, i)
        arr.append(temp) # making a array of random int values
    x.append(i)
    start = timeit.default_timer()
    mergeSort(arr, 0, i-1)
    end = timeit.default_timer()
    y.append(end - start) # storing the execution time to sort the array
    n.append(i*log2(i)) # Calculating nlogn

plt.plot(x, y, label='merge sort')
plt.plot(x, n, label='nlogn')
plt.legend()
plt.xlabel('array size ')
plt.ylabel('execution time (s)')
plt.title('Merge Sort')
plt.show()

该程序的输出：

例外的输出：

我们知道，合并排序算法的时间复杂性是o（nlogn），但是当我试图尝试绘制它非常低。

请建议我一种绘制图形或此代码中一些修改的方法。

Answer 1

小阵列的时间差异将受小组拟合的高速缓存水平的影响。即使对于大型数组，缓存也会影响排序时间，而不是计算操作数量（比较和移动）。还有Python的开销，对于同一合并排序算法，超过50倍的速度是C或C ++实现的速度。对于大N ） / log2（2^20）= 1.05，log2（2^26） / log2（2^25）= 1.04，等等。