二、排序问题的上限、下限

已经知道，基于比较的排序问题的上限是O(nlogn)；可以证明，基于比较的排序问题的下限也为Ω(nlogn)。因此，基于比较的排序算法的时间代价就是Θ(nlog n)。