Aloraman
А по этим 80 гигам можно несколько раз пробежать?
Прочитать первый раз, набрать статистику сколько раз какой префикс 1-2 байта встречается, зааллоцировать 256/65536 массивов под них и заполнить, прочитав второй раз? Потом параллельно просортировать
Правда тут уж недалеко и до написания своего B+/B*, проще сразу в натив уходить
Вот это самый годный метод, к тому же масштабируемый хорошо. Ждал, когда кто-то додумается. Поскольку там хорошее распределение (как у рандома), то не нужно два раза бегать. Просто аллоцируем списки сразу с капасити среднестатистическим, а потом перегруженные сами вырастут, это делается за амортизированную константу по времени. Поскольку списки теперь можно делать маленькие, то все будет хорошо с точки зрения хипа (не обязательно класть в LOH). Заодно можно сортировать параллельно, и любым алгоритмом (не обязательно cache-friendly), потому что списки маленькие, и целиком могут влезать в кеш.