我正在尝试研究如何有效地排序不适合内存的巨大数据集.高级别的明显答案是使用一些标准算法对一大堆适合内存的块进行排序,将这些块写入磁盘,然后合并它们.合并它们是问题所在.
假设数据分为C块,所以我要合并C文件.如果我在一次传递中进行C-way合并,那么从技术上讲,我有一个O(N ^ 2)算法,尽管只需要执行O(N)写入磁盘.如果我迭代地将它们合并到C/2文件,然后是C/4文件等,那么我有一个O(N log N)算法,但是一个必须执行O(N log N)写入磁盘,因此一个巨大的常数.
这个难题的典型解决方案是什么？有什么好的吗？