从阅读从维基百科上的排序算法此的文章，它似乎是smoothsort是最好的排序算法存在。它拥有顶级的性能在所有类别：最好的，平均和最差。没有任何类别击败它。它还具有恒定的内存需求。唯一的缺点是，它是不稳定的。

From reading this article from Wikipedia on sorting algorithms, it would seem that smoothsort is the best sorting algorithm there is. It has top performance in all categories: best, average, and worst. Nothing beats it in any category. It also has constant memory requirements. The only downside is that it isn't stable.

这可难倒timsort在内存中，它打败快速排序在这两个最坏情况下的性能和内存。

It beats timsort in memory, and it beats quicksort in both worst-case performance and memory.

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

But I never hear about smoothsort. Nobody ever mentions it, and most discussions seem to revolve around other sorting algorithms.

这是为什么？

推荐答案

大澳的表现是伟大的发表论文，但在现实世界中，我们必须看看常数也。快速排序一直是首选不稳定，就地，内存中的排序了这么久，因为我们可以非常有效地实施其内部循环的算法，这是非常缓存友好。即使可以实现smoothsort的内环尽可能有效，或几乎一样有效，因为快速排序的，你可能会发现它的高速缓存未命中率使得它更慢。

Big-O performance is great for publishing papers, but in the real world we have to look at the constants too. Quicksort has been the algorithm of choice for unstable, in-place, in-memory sorting for so long because we can implement its inner loop very efficiently and it is very cache-friendly. Even if you can implement smoothsort's inner loop as efficiently, or nearly as efficiently, as quicksort's, you will probably find that its cache miss rate makes it slower.

我们减轻，花多一点的努力，选择好支点（减少病理性的病例）和检测病理情况下快速排序的最坏情况下的性能。查找 introsort 。 Introsort第一次运行快速排序，但切换如果它检测到过度的递归（这表明一个病态的情况下快速排序），以堆排序。

We mitigate quicksort's worst-case performance by spending a little more effort choosing good pivots (to reduce the number of pathological cases) and detecting pathological cases. Look up introsort. Introsort runs quicksort first, but switches to heapsort if it detects excessive recursion (which indicates a pathological case for quicksort).