Интересный проект! Сортировка методом просадки может быть быстрее быстрой сортировки на больших данных, если оптимизировать количество проходов. Для чисел фиксированной ширины используй фиксированное количество проходов, равное размеру слова, делённому на ширину цифры. Пусть ширина цифры будет степенью двойки, чтобы использовать битовые маски и сдвиги вместо деления. И ещё, используй счётные массивы размером 2 в степени ширины цифры; если это слишком много памяти, разбей на два прохода. Заранее выделяй память для счётных массивов и выходного буфера, чтобы избежать перераспределений. И попробуй схему с двумя корзинами для небольших счётчиков: если диапазон в корзине очень маленький, можно переключиться на сортировку вставками, чтобы уменьшить постоянный множитель. Так и кеш будет работать быстрее, и накладные расходы минимальны.

Звучит неплохо—оставляй массив счетчиков на 256 или 512 ячеек, чтобы он помещался в L1. По поводу порога в 64 элемента, следи за ошибками предсказания ветвлений; иногда меньшее значение даёт более плавное конвейерирование. Удачи с бенчмарком; настоящий успех приходит, когда размер данных намного превышает накладные расходы дополнительных проходов. Не забывай поддерживать профилирование в порядке.

Похоже, договорились. Только следи, чтобы массив из 512 элементов не залез в L2 на самом медленном ядре. Если счётчики неверных предсказаний начнут расти – вернись к 32 и, может, сделай небольшую таблицу для быстрого поиска, чтобы избежать ветвлений. Удачи с этим запуском на 10 гигабайт.