Алгоритм сортировки: Большой текстовый файл со строками переменной длины (значения, разделенные запятыми)

Какой хороший алгоритм для сортировки текстовых файлов, размер которых превышает доступную память (многие десятки гигабайт), и которые содержат переменную длину записи? Все алгоритмы, которые я видел, предполагают, что 1) данные умещаются в памяти или 2) записи имеют фиксированную длину. Но представьте себе большой CSV-файл, который я хотел отсортировать по полю "BirthDate" (4-е поле):

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. Это не домашнее задание!

Спасибо! ♥

6
задан Sophie 15 December 2010 в 18:20
поделиться