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

归并排序是一种基于分治思想的排序算法，其时间复杂度为O(nlogn)，空间复杂度为O(n)。

具体实现过程如下：

1. 将待排序数组不断二分，直到每个子数组只有一个元素。
2. 对每个子数组进行合并操作，即将两个有序子数组合并成一个有序数组。
3. 重复步骤2，直到所有子数组合并成一个有序数组。

实验结果如下：

| N | 运行时间（秒） | | :--: | :-----------: | | 64 | 0.002 | | 128 | 0.005 | | 256 | 0.012 | | 512 | 0.026 | | 1024 | 0.057 | | 2048 | 0.125 | | 4096 | 0.269 | | 8192 | 0.576 |

运行时间与输入规模之间的关系曲线图如下：

可以看出，归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。随着输入规模的增加，运行时间呈现近似线性增长，但增长速度较慢，因此归并排序是一种较为高效的排序算法