如何在2n RAM中对n ^ 2个元素进行排序

Question

有人可以告诉我如何使用2n量的RAM对n ^ 2个元素进行排序.一种可能的方法是分成n个大小为n的数组.然后在n个元素中进行合并排序,最后在n个数组上保持n个堆的大小.但是,这意味着每次放置一个元素时,我都会进行磁盘读取,每次完成n个元素时,我都会进行磁盘写入.有更好的建议吗？谢谢.

Answer 1

这是不可能的。仅元素就需要 n^2 内存。

如果不考虑这种明显的内存消耗，我推荐一种就地排序算法，例如堆排序。它将占用 O(1) 额外空间。

如果您正在寻找一种外部排序算法，其中外部存储不计算在内，而仅计算内部存储，我建议使用自下而上的合并排序。您可以根据需要让它消耗尽可能多或尽可能少的内存；要消耗大约 2n 内存，请始终从每个部分排序的集合中读取 n/2 个元素，并将它们合并到另一个包含 n 个元素的数组中；然后将结果写回磁盘（最好写入单独的文件）。