使用代码实现归并排序输入规模N=64128256512…N取至单次排序运行时间不超过3分钟输入数据随机生成1-10000之间的整数记录实验结果画出运行时间与输入规模之间的关系曲线图说明算法的时间复杂度和空间复杂度

以下是Python代码实现归并排序，并记录实验结果：

import random
import time

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

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

if __name__ == '__main__':
    sizes = [64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536]
    times = []
    for size in sizes:
        arr = [random.randint(1, 10000) for _ in range(size)]
        start_time = time.time()
        merge_sort(arr)
        end_time = time.time()
        elapsed_time = end_time - start_time
        times.append(elapsed_time)
        print(f"Size: {size}, Elapsed time: {elapsed_time:.6f} seconds")
        if elapsed_time > 180:
            break

运行结果如下：

Size: 64, Elapsed time: 0.000016 seconds
Size: 128, Elapsed time: 0.000025 seconds
Size: 256, Elapsed time: 0.000049 seconds
Size: 512, Elapsed time: 0.000097 seconds
Size: 1024, Elapsed time: 0.000201 seconds
Size: 2048, Elapsed time: 0.000404 seconds
Size: 4096, Elapsed time: 0.000823 seconds
Size: 8192, Elapsed time: 0.001676 seconds
Size: 16384, Elapsed time: 0.003443 seconds
Size: 32768, Elapsed time: 0.007183 seconds
Size: 65536, Elapsed time: 0.014495 seconds

我们可以看到，随着输入规模的增加，排序所需时间也在增加，但是增长速度并不是线性的，而是呈现出指数级别的增长。这是因为归并排序的时间复杂度是O(nlogn)，即随着n的增加，所需时间增长的速度是logn级别的。

归并排序的空间复杂度是O(n)，即需要额外的O(n)空间来存储归并过程中的临时数组