arrays - 为什么快速排序平均比其他排序快？

Question

正如我们所知，快速排序的平均性能为 O(n*log(n))，但合并和堆排序的平均性能也为 O(n*log(n))。所以问题是为什么快速排序平均速度更快。

Answer 1

Wikipedia suggests :

Typically, quicksort is significantly faster in practice than other O(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices that minimize the probability of requiring quadratic time. Additionally, quicksort tends to make excellent usage of the memory hierarchy, taking perfect advantage of virtual memory and available caches. Although quicksort is not an in-place sort and uses auxiliary memory, it is very well suited to modern computer architectures.

另请查看 comparison with other sorting algorithms在同一页上。

另见 Why is quicksort better than other sorting algorithms in practice?在 CS 网站上。