如果您被给予：
- 一定数量的数据
- 大小为数据大小一半的内存
- 部分数据已排序
- 您不知道已排序数据的大小
你会选择哪种排序算法？我在讨论插入和快速排序。我知道插入排序的最佳情况是O（n），但最坏的情况是0（n2）。此外，考虑到内存有限的事实，我会将数据分为两部分，对每一部分进行快速排序，然后将所有数据合并在一起。对于O（n log n）的净运行时间，拆分数据将需要O（n）时间，合并数据将需要0（n），使用快速排序对数据进行排序将需要O。
有人对如何改进这一点有什么建议吗？
您的类似合并的方法似乎非常合理。更一般地，这种类型的排序算法被称为外部排序算法。这些算法通常如您所描述的那样工作——将数据的某个子集加载到内存中，对其进行排序，然后将其写回磁盘。最后，使用合并算法将所有内容重新合并在一起。加载量和使用何种排序算法的选择通常是主要关注的问题。我将主要关注排序算法的选择。
您对quicksort最坏情况行为的担忧一般来说无需担心，因为如果您随机选择枢轴，则运行时非常糟糕的概率很低。即使数据已经排序，随机枢轴策略也能很好地工作，因为它没有最坏情况下的输入（除非有人知道你的随机数生成器和种子）。你也可以使用像introsort这样的快速排序变体，它没有最坏的行为，作为你的排序算法，以避免这种最坏的情况。
也就是说，由于您知道数据已经部分排序，因此您可能需要为排序步骤研究自适应排序算法。您已经提到了插入排序，但有更好的自适应算法。如果内存不足（正如您所描述的），您可能需要尝试研究平滑排序算法，该算法具有最佳情况下的运行时O（n）、最坏情况下的执行时O（n-logn），并且只使用O（1）内存。它不像其他一些算法（如Python的timsort、自然合并排序或笛卡尔树排序）那样具有自适应性，但内存使用率较低。它也没有好的快速排序快，但如果数据真的大部分都经过了排序，它可以做得很好。
希望这能有所帮助！
从表面上看，我会把&用quicksort征服并到此为止。许多算法问题都考虑过度了。
现在，如果您确实有测试数据要使用，并且确实想掌握这些数据，那么在中间添加一个抽象类并进行基准测试。我们可以整天东拉西扯，但知道数据已经部分排序，你就必须进行测试。在大多数快速排序实现中，排序后的数据会带来最坏的性能。
考虑有许多排序算法，其中一些更适合排序集。此外，当您知道一个集合已排序时，您可以在n次内将其与另一个集合合并。因此，当您比较添加单个（n）过程和大大减少快速排序到（n2）时间的机会时，首先识别已排序数据块可能会节省大量时间。