为什么smoothsort不常见？

Question

从阅读此文章从维基百科上的排序算法,它似乎是smoothsort是最好的排序算法存在.它在所有类别中都有最佳表现:最佳,平均和最差.在任何类别中都没有什么比这更好的了.它还具有恒定的内存要求.唯一的缺点是它不稳定.

它在内存中击败了timsort,并且它在最坏情况下的性能和内存方面都快速进入.

但我从来没有听说过smoothsort.没有人提到它,大多数讨论似乎围绕其他排序算法.

这是为什么？

Answer 1

Big-O性能非常适合发布论文,但在现实世界中我们也必须考虑常量.Quicksort长期以来一直是不稳定,就地内存排序的首选算法,因为我们可以非常高效地实现其内部循环,并且它非常适合缓存.即使你可以像quicksort一样有效地或几乎同样有效地实现smoothsort的内部循环,你可能会发现它的缓存未命中率使它变慢.

我们通过花费更多的努力选择好的枢轴(减少病理病例的数量)和检测病理病例来减轻quicksort的最坏情况表现.查看内省.Introsort首先运行快速排序,但如果它检测到过多的递归(这表示快速排序的病态情况),则切换到heapsort.

Answer 2

更好的渐近并不意味着更好的表现(虽然通常情况就是如此).隐藏常数可能会大几倍,导致它比相对较小的数组(相对较小的数组,实际上可能是任意大小,10 ¹⁰⁰,相对较小)具有更慢的速度(相同甚至最差的渐近复杂度)例如.这是渐近分析).但我对smoothsort隐藏的常量一无所知.

例如,有一个用于查找k阶统计量的O(n)最坏时间算法,但它太复杂了,在大多数情况下,O(n log n)最坏情况版本优于它.

此外,还有一个有趣的比较:

......正如你所看到的,Timsort和Smoothsort都没有削减芥末.在所有情况下,Smoothsort都比STL排序更差(即使使用std:bitset替换为原始位操作)...