如果以前重复过这种情况，我深表歉意，但我找不到任何使用我选择的措辞的帖子。我正在准备面试，并且一直在阅读有关外部排序的信息。例如，如果要对几个 32 位整数的硬盘进行排序，可以进行计数排序，并使用 64 位计数器对 32 位整数进行计数。然后，对于每一个可能的 32 位整数值，您都会有一个计数器来表示它。您还可以对类似的事情使用外部合并排序，花费 O(nlogn) 时间而不是 O(1) 时间。但是，我一直在考虑一个可能很常见的案例，但我想不出最好的方法 - 将新数据添加到可能跨越许多硬盘的一堆排序文件中。
如果内存中有数据，则可以使用堆（优先队列）在登录时间内完成此插入。但是，我们不能从硬盘空间中进行堆。使用列表，您必须使用 O(logn) 搜索来查找数据的位置（对于二进制搜索，已排序），然后将其余数据向后或向前颠簸，或者您可能不必根据实现进行任何移动容器（数组、链表等）。然而，在硬盘世界中，读写比在 RAM 中要昂贵得多，因此在某处插入数据然后转移（重写）其余数据似乎非常昂贵。你们有什么技术可以推荐给我吗？我很乐意阅读自己，我只是找不到正确的方式来表达我的问题以找到任何信息。谢谢！
如果您在此处（或其他地方）查找“外部排序”，您会发现有关您所描述内容的讨论。external-sorting 也是这里的一个标签。
然而，在硬盘世界中，读写比在 RAM 中要昂贵得多，因此在某处插入数据然后转移（重写）其余数据似乎非常昂贵。
外部排序适用于您没有足够内存（或在大多数情况下有足够的“每个进程”）在内部进行排序的情况。数据集太大而无法一次保存在内存中的情况并不少见。因此，您接受 I/O 绑定排序的更高运行时间成本。
我会说阅读您的排序数据文件，阅读您想要排序并添加到那里的文件，扣上计数器并用新计算的数据文件覆盖排序的数据文件。在现代磁盘系统上，直接读取比随机读取要便宜得多，而且无论如何您都需要为找到的每个 int 提供一个位置，因此对整个卷的单次顺序读取将比对单个扇区的约 32 次读取耗时更少每个要排序的文件数。
另外，我想说对 32 位整数进行排序最好在结果已经以计数器的形式完成，特别是在像“几个硬盘”这样的超大规模时，你会期望在 32 的几乎每个桶中至少有 1-位空间，因此存储 64 位 *2^32 可能小于 2^33 32 位零，然后是 2^32 零...
如果您在内存中有空间来保存文件，并且您有一组最小元素为 k 的数字，您将不得不重新写入文件中大于 k 的所有数字。没有办法解决这个问题。他们都将不得不改变至少一个位置。
如果您希望利用大多数数组已经排序的事实，并且您在内存中有空间这样做，那么对插入的元素进行排序并将其与大于其最小成员的元素列表合并是一个好的，快速的方法来做到这一点。例如：
磁盘：
1 2 3 4 5 6 8 10 11 12
插入：9 7 13
对插入进行排序：
7 9 13
在磁盘上找到适用的排序列表的子集：8 10 11 12
合并元素（如在 Mergesort 中：）
7 8 9 10 11 12 13
将它们复制回磁盘：
1 2 3 4 5 6 7 8 9 10 11 12 13
另一方面，如果您的内存空间远小于列表的总大小，则可能建议使用其他技术。例如：
1 2 3 4 .. 1000 1002 1003... 999,998, 1,000,000...
作为您在磁盘上的列表和
1001, 999,999
作为你的插入。在这种情况下，您将需要遍历每个元素，计算插入列表中小于该元素的元素数量，然后执行此操作。在这个简单的例子中，简单的计数器非常快——你可以看到 1,000,0000 需要两次跳转。如果插入的数量可能比较大，您可以对插入进行排序，然后对该元素使用二进制搜索来查找较大数组中的每个元素可能位于的位置。这将为您提供有关可以复制多少项目的信息。因此，顶部的相应跳转值为：
0 0 0 0 ... 0 1 1 ... 1 2
希望您能看到一个相当明显的方法，您可能希望通过该方法决定将一个插入元素写入磁盘。