c++ - 如何对整数数组实现归并排序？

Question

我有一个作业要求使用归并排序对一百万个 int 数组进行排序。我学习合并排序的方法是使用递归的拆分例程和合并例​​程。我将如何使用递归拆分数组？我是否需要总共制作三个数组，其中两个数组的大小是原始数组的一半？

我可能没有说清楚，因为我现在对整个概念感到困惑。

我不会用 Python 编写代码，也不知道 trimsort 是什么。

Answer 1

要按顺序进行合并排序，您应该在递归函数中执行以下操作:

1. 检查数组的大小:如果小于或等于 2，则对 数组并返回它。
2. 将数组分成两部分，并为每一半调用递归函数。
3. 合并来自第 2 步函数调用的两个排序数组的结果。

输入的大小实际上对你如何解决它并不重要，除非你想并行处理。