Насколько я знаю сортировка слиянием самая быстрая если нельзя Radix Sort приклеить.
Но сортировать надо чуть умнее чем стандартное описание.

1. Находим ВСЕ монотонные ( отсортированные или отсортированные наоборот) ПОДучастки последовательности.
2. Сливаем сортированные последовательности друг с другом ( соизмеримо с размерами последовательностей)
3. Делаем 1 и 2 пока не отсортируем.

ВЫГОДЫ:
Кеш френдли, особенно в случае баз данных всяких.
Нет плохих случаев ! ( и это еще не все ! )
Лучшее время O(N) ( в случае полностью отсортированной последовательности или отсортированной наоборот) худшее O(N*LOGN) ( надо нехило потрудиться чтобы найти такой случай).


НЕДОСТАТКИ:
требует дополнительной памяти для эффективной реализации. (может кто знает другую ? )
эффективная реализация довольно сложна.