timsort

[netch80]

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

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

Comments

[gegmopo4.livejournal.com]

Тоже баян. Что сама статья, что алгоритм, который уже широко используется. ;)

[netch80.livejournal.com]

Это журнал для того, что мне интересно сказать, а не для свежих новостей.

За третью реплику про "баян" забаню. Ничего личного.

[gegmopo4.livejournal.com]

Да нет, я просто удивляюсь. Ведь и Питон, кажется, используете, а там timsort. Хотя, конечно, использовать — не значит погружаться в такие мелочи.

Если мне не изменяет память, на Хабре, где статьи обычно идут косяками, про timsort тоже было несколько статей.

[gegmopo4.livejournal.com]

За «баян» прошу меня простить. Извините, если это выглядело оскорбительно и грубо, я не имел в виду троллить.

[http://users.livejournal.com/_slw/]

гм. памяти n. у binary tree такие же характеристики, кстати

[netch80.livejournal.com]

Там (у двоичного дерева) постоянный коэффициент сильно выше. И ещё timsort сокращает количество сравнений. В местах, где сравнения дорогие, а перестановки дешёвые, он может оказаться эффективнее на порядок.

В табличке в статье не приводится оценок количества сравнений и перестановок в зависимости от размера, а зря.

Есть ещё характеристики, которые не приведены там и могут существенно повлиять. Например, сортировка Бэтчера принципиально параллелится изначально. Timsort близка к этому. Хоар параллелится хуже, хотя в общем случае таки неплохо.
В общем, тут есть куда копать:)

[http://users.livejournal.com/_slw/]

там еще не уточняется какой именно памяти надо N. при больших объектах это тоже существенно.

[gegmopo4.livejournal.com]

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

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