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

注：由于机器性能、语言环境等因素的影响，以下时间复杂度和空间复杂度分析仅供参考，具体情况需要根据实验结果进行分析。

归并排序

归并排序是一种稳定的排序算法，时间复杂度为O(nlogn)，空间复杂度为O(n)。归并排序的基本思想是将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将这些有序的子序列合并成一个有序的序列。

快速排序

快速排序是一种不稳定的排序算法，时间复杂度为O(nlogn)，空间复杂度为O(logn)。快速排序的基本思想是通过一趟排序将待排序序列分成两部分，其中一部分的所有元素均比另一部分的所有元素小，然后再按此方法对这两部分分别进行快速排序，直到整个序列有序。

比较

归并排序和快速排序都是基于分治思想的排序算法，它们的时间复杂度都为O(nlogn)，但归并排序是一种稳定的排序算法，而快速排序是一种不稳定的排序算法。此外，归并排序的空间复杂度为O(n)，而快速排序的空间复杂度为O(logn)。

根据实验结果，可以得出以下结论：

1. 在数据规模较小的情况下，归并排序和快速排序的运行时间差异不大。

2. 随着数据规模的增大，快速排序的运行时间逐渐优于归并排序。

3. 当数据规模达到一定程度时，归并排序的运行时间会超过快速排序，这是由于归并排序需要额外的空间来存储临时数组。

因此，对于数据规模较小的情况，可以选择归并排序或快速排序；对于数据规模较大的情况，建议选择快速排序