任何比较排序在最好情况下都要经过Ω(nlgn)，即比较排序的下界为Ω(nlgn)。
合并排序和堆排序都是渐进最优的。
要突破Ω(nlgn)，就要进行非比较排序。计数排序、基数排序和桶排序都有非比较的一些操作来确定排序顺序，它们可以达到线性运行时间。
这三种排序都是以空间换时间。应用的不广，先不细看了。
任何比较排序在最好情况下都要经过Ω(nlgn)，即比较排序的下界为Ω(nlgn)。
合并排序和堆排序都是渐进最优的。
要突破Ω(nlgn)，就要进行非比较排序。计数排序、基数排序和桶排序都有非比较的一些操作来确定排序顺序，它们可以达到线性运行时间。
这三种排序都是以空间换时间。应用的不广，先不细看了。
原文：https://www.cnblogs.com/jackson-zhou/p/8419798.html