Сортировка огромного текстового файла: реализовать алгоритм

merge sort на первый взгляд должен подойти

не сталкивался с таким

1) сортировка слиянием должна подойти

2) есть вероятность, что вы что-то делаете не так. зачем нужен отсортированный огромный текстовый файл, который не помещается в память? что с ним дальше планируется делать? по нему все равно будет неудобно искать, т.к. линии разной длины

в обыденной жизни строят внешние индексы (можно частичные) и дальше работают через них..

чо, институт начался? или собеседовние? :)) мержсорт, да

прыгнуть на середину и пройти до конца текущей линии это все равно быстрее, чем искать линейно в файле массой овер 1 терабайт.

хотя хз зачем это может понадобиться. такой файл с таким количеством строк.

помещается целиком в виртуальную память

Виртуальная память ограничена лишь разрядностью шины, т.е. для AMD64 48бит, что есть 256Тб. Но т.к. в вопросе нет указания архитектуры, то виртуальное адресное пространство не ограничено. Когда MMU перестанет находить нужные адреса в памяти, то начнется свапинг и дальше ты упрешся только в диск.

Ну а почитать, например, вот http://cseweb.ucsd.edu/~gmporter/papers/tritonsort-nsdi11.pdf У них radix sort внутри.

прям компутер ссаенс

пиши тег лаболаторная

Вообще-то это компутер сайенс и есть.

строк(линий)

кекеке

ТС хочет поразрядную сортировку, или может быть даже битонную, а вы тут зашли нагадить в топик, о котором ничего не можете сказать.

да и соси шланг

Выше правильно написали, по нормальному нужно индексы строить, и через них работать.
Без индексов:
https://en.wikipedia.org/wiki/Merge_sort
https://en.wikipedia.org/wiki/External_sorting
Т.е. идея в том, чтобы разбить файл на маленькие куски, сначала их отсортировать, а потом объеденить их по очереди.

Залей его построчно в таблицу какой-нибудь SQL БД и там отсортируй-поиндексируй, как тебе нравится.

man sort

ТС хочет поразрядную сортировку, или может быть даже битонную

ТС хочет сдать сессию и присунуть какой-нибудь девочке. Инфа соточка.

попробуй начни со смены ника и авы

А почему не мальчику? И вообще, я допускаю, что он просто никогда не сталкивался с данной проблемой, а тут появилась задача и её необходимо решить, и дело вовсе не в сессии.

Вопрос к знатокам всего

Кнут — знаток всего :)

random sort подойдёт лучше, чем merge sort

Как уже написали: делаешь любую сортировку для чанков, влезающих в память, потом сливаешь по два чанка в один, как в сортировке слиянием.

Лицо часто ломают? Или это ты только в интернете такой дерзкий?

единственный нормальный ответ в треде. как грится, все уже украдено до нас..

Спасибо огромное всем за ответы!

Сортировка больших файлов