Есть такой чувак, Yijie Han, работает (по крайней мере работал) в University of Missouri at Kansas City. В 2004м выпустил работу Han, Yijie (2004), «Deterministic sorting in O(n log log n) time and linear space», Journal of Algorithms. Cognition, Informatics and Logic 50 (1): 96–105, , кратко - алгоритм сортировки за O(n log log n). Ни одной реализации найти не удалось, более менее адекватное описание на сайте ИТМО. Где-то прочел, что в реальной жизни он не применим. Почему? Вообще есть более подробное описание? Реализации? Хотелось бы попробовать.