Здравствуйте, Hobbes, Вы писали:

H>3 слова: внешняя сортировка слиянием. Куски до слияния можно хоть поразрядной сортировкой сортировать, хоть на несколько ядер параллелить (если RAM позволяет), хоть что делать, пока не упёрлись в I/O.

H>Или применить обратный подход: зная распределение данных по разрядам (нас интересует, с какого символа данные реально отличаются), распиливаем входные данные на файлы по нескольким первым разрядам, каждый файл сортируем в памяти, после этого склеиаем отсортированные файлы.

То есть, комбинация радикс сорта и любого другого алгоритма.

Здравствуйте, Hobbes, Вы писали:

H>3 слова: внешняя сортировка слиянием.

Эффективность у него так себе.

H>Или применить обратный подход: зная распределение данных по разрядам (нас интересует, с какого символа данные реально отличаются), распиливаем входные данные на файлы по нескольким первым разрядам, каждый файл сортируем в памяти, после этого склеиаем отсортированные файлы.

То есть, комбинация радикс сорта и любого другого алгоритма.