分别实现归并排序、快速排序输入规模N=64128256512…N取至单次排序运行时间不超过3分钟输入数据随机生成1-10000之间的整数写出代码做出运行时间与输入规模之间的关系曲线图说明算法的时间复杂度和空间复杂度根据曲线图比较3种排序算法的优劣。

归并排序代码：

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):
    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

快速排序代码：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = [x for x in arr[1:] if x < pivot]
    right = [x for x in arr[1:] if x >= pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

测试代码：

import random
import time

n = 64
while True:
    arr = [random.randint(1, 10000) for _ in range(n)]
    start = time.time()
    # 使用归并排序或快速排序
    arr = merge_sort(arr)
    # arr = quick_sort(arr)
    end = time.time()
    if end - start > 180:
        break
    n *= 2

时间复杂度：

归并排序和快速排序的时间复杂度均为O(nlogn)，但是快速排序的常数因子更小，因此在实际应用中表现更优秀。

空间复杂度：

归并排序需要额外的O(n)空间用于合并两个有序数组，而快速排序只需要O(logn)的空间用于递归调用栈。

优劣比较：

从时间复杂度和空间复杂度的角度来看，快速排序是最优秀的。但是在某些特定情况下，快速排序的性能可能会退化，例如当输入数据已经有序或近乎有序时，快速排序的时间复杂度会退化到O(n^2)，此时归并排序表现更优秀。因此在实际应用中需要根据具体情况选择合适的排序算法