你们中的大多数人都会意识到这一点，但对我来说这有点令人惊讶:使用合并排序(保持信息总量不变)对 96 个每个大小为 4Mb 的文件进行排序比对 6 个 64Mb 的文件进行排序要快得多).我偶然发现了这个发现。所以这就引出了一个问题，合并排序的最佳输入文件大小是多少？
我假设排序时间(y 轴)和文件数量(x 轴)之间存在曲线形状的关系。是否有一种算法，它是更多的经验法则还是只是尝试几种不同的文件大小？影响这一点的明显因素是:
* 操作系统可以同时打开的最大文件数。
* 硬盘读写速度
欢迎任何引用!
最佳答案
如果您的排序涉及移动文件，那么“最快”排序算法的常规衡量标准并不适用。对于移动文件，更快的排序算法将包括最小化文件写入次数。
可以使用选择排序，并且非常接近可能的最小交换次数，但同样，在最坏的情况下，每个文件必须写入两次:一次，当它被交换出来为文件腾出位置时属于那里，一旦时间到了，它就会被换到它应该在的地方。
有一种算法最多执行 n+1 次分配。 “交换”(这是大多数排序算法使用的)涉及三个分配(使用临时变量)。通过进行选择排序而不实际交换任何东西，这几乎可以工作。通过将每个选定的项目写入新内存，或者将排序顺序保存在内存中，然后在事后在同一内存空间中重新组织文件(碎片整理方式)。该算法在数据复制方面确实是最小的。当复制项目成本很高(在磁盘上排序数据)时，这是理想的选择。
关于algorithm - 如何确定合并排序的最佳文件大小？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4355192/