Now that we have seen two algorithms for sorting that are more efficient than the ones described in the previous chapter, how do we know that they are as efficient as a sorting can be? Can we make algorithms that are even faster? We will see in this section that we have reached our asymptotic limit of efficiency, that is, a comparison-based sorting will have a minimum time complexity of θ(m lg m), where m is the number of elements.

Suppose we start with an array of m elements. For the time being, let's assume they are all distinct. After all, if such an array is a possible input, we need to consider this case as well. The number of different arrangements possible with these elements is m!. One of these arrangements is the correct sorted one. Any algorithm that will sort this array using comparison will have to be able to distinguish this particular arrangement from all others using only comparison between pairs of elements. Any comparison divides...