排序一个巨大的数组

什么是排序一个巨大的数组的最佳方式。说我有1G RAM，阵列是16G。什么是最有效的方法来做到这一点？我有足够的磁盘文件。排序一个巨大的数组

您打算使用哪种编程语言？你似乎最关心内存使用情况。虚拟内存的状态是什么;你甚至需要关心吗？ *您对'最佳'*的定义是什么？ - 时间，最小化交换或其他？ – 2011-02-24 02:37:46

@ p.campbell不是一个实际的问题。关注算法和解决方案。谢谢:) – 2011-02-24 02:38:52

@ p.campbell是啊有点。我以前遇到过另一个大文件问题。所以想出了这个。仍在为亚马逊采访做准备。 LOL〜 – 2011-02-24 02:52:07

分割成块并将512MB一次分类为32个文件。然后将这些文件合并排序成一个文件。

2011-02-24 02:38:52 recursive

如果它是一个整数数组，你可以用一个朴素的基数排序(O(n))并且根本不使用RAM。第一个问题是“它是什么样的数据？”。如果它的任意数据，那么外部mergesort可能是你最好的选择。

-tjw

2011-02-24 03:06:33

回答