[expl]

Ага, а в 1/10 - сортировку слиянием, т.к. это единственная сортировка с O(n * log n) с сохранением порядка сортировки без расширения ключа.
Она жрет память размером с сортируемый массив, но общий алгоритм сортировки с сохранением порядка и не жрущий память вряд ли существует (если не брать O(n * n))