归并排序时间复杂度分析：Python实现及运行时间曲线图

以下是Python实现的归并排序代码：

import random
import time

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

# 生成随机数据
def generate_data(n):
    return [random.randint(1, 10000) for _ in range(n)]

# 测试函数
def test(n):
    arr = generate_data(n)
    start_time = time.time()
    arr = merge_sort(arr)
    end_time = time.time()
    assert arr == sorted(arr)
    return end_time - start_time

# 绘制图表
import matplotlib.pyplot as plt

x = [64, 128, 256, 512, 1024, 2048, 4096, 8192]
y = [test(n) for n in x]
plt.plot(x, y)
plt.xlabel('Input Size')
plt.ylabel('Time (s)')
plt.title('Merge Sort')
plt.show()

运行结果如下图所示：

从上图可以看出，随着输入规模的增加，归并排序的运行时间呈线性增长趋势，这与归并排序算法的时间复杂度O(n log n)相符。