Какой на сегодняшний день наиболее оптимальный алгоритм сортировки? Массивы в памяти. Время сравнения и обмена — одного порядка. Интересует алгоритм, который ко всему прочему сортирует почти отсортированные последовательности за время меньшее чем n*log(n).

Вообщем, что у меня есть на настоящий момент: quicksort с 3-way partitioning и random pivot + insertion sort для короткий подпоследовательностей. Работает неплохо. Random pivot вроде бы даёт некоторую adaptiveness, но мне кажется, что есть более эффективные алгоритмы. Вопрос какие?