timsort

[netch80]

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

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

Comments

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

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