algorithm - 排序算法 : Big text file with variable-length lines (comma-separated values)

Question

对于大于可用内存(数十千兆字节)且包含可变长度记录的文本文件进行排序，什么是好的算法？我见过的所有算法都假设 1) 数据适合内存，或 2) 记录是固定长度的。但是想象一下我想按“出生日期”字段(第 4 个字段)排序的大 CSV 文件:

Id,UserId,Name,BirthDate
1,psmith,"Peter Smith","1984/01/01"
2,dmehta,"Divya Mehta","1985/11/23"
3,scohen,"Saul Cohen","1984/08/19"
...
99999999,swright,"Shaun Wright","1986/04/12"
100000000,amarkov,"Anya Markov","1984/10/31"

我知道:

1. 这将在一台 机器(非分布式)上运行。
2. 我要运行它的机器会有多个处理器。
3. 我要排序的文件可能大于机器的物理内存。
4. 一个文件包含可变长度的行。每行将包含固定数量的列(分隔符分隔的值)。文件将按特定字段(即文件中的第 4 个字段)排序。
5. 理想的解决方案可能是“使用这个现有的排序实用程序”，但我正在寻找最好的算法。
6. 我不希望得到完整编码的有效答案；更多的内容是“检查一下，这是它的工作原理，或者这就是为什么它能很好地解决这个问题。”我只是不知道去哪里看...
7. 这不是家庭作业!

谢谢! ♥

Answer 1

这类算法称为外部排序。我将从检查 Wikipedia entry 开始.它包含一些讨论和指示。