timsort

[netch80]

Отличный пример того, как происходят прорывы вроде бы в давно изведанных областях.

Гарантированно устойчивое O(n log n), с отличным постоянным коэффициентом и стабильным порядком. Хотя реализацию на пальцах не объяснить.

Comments

[gegmopo4.livejournal.com]

Именно так в Python и Java. Сравнение — это вызов пользовательского кода (даже для встроенных типов несколько виртуальных вызовов), а перестановка — пара машинных инструкций.

Количество сравнений и перестановок зависит не только от размера, но и от распределения. Для совершенно случайного получим одно, но timsort выгоден тем, что очень хорошо ведёт себя на неслучайных данных. И тут уже зависит от фантазии тестировщика, какие неслучайные последовательности он посчитает близкими к реальности.