## 7.8 Lower Bounds for Sorting Only by Comparison of Keys We have developed Θ (*n* lg *n*) sorting algorithms, which represent a substantial improvement over quadratic-time algorithms. A good question is whether we can develop sorting algorithms whose time complexities are of even better order. We show that, as long as we limit ourselves to sorting only by comparisons of keys, such algorithms are not possible. Although our results still hold if we consider probabilistic sorting algorithms, we obtain the results for deterministic sorting algorithms. (See [Section 5.3](LiB0072.html#840) for a discussion of probabilistic and deterministic algorithms.) As done in [Section 7.3](LiB0054.html#647), we obtain our results under the assumption that the *n* keys are distinct. Furthermore, as discussed in that section, we can assume that the *n* keys are simply the positive integers 1, 2, …, *n*, because we can substitute 1 for the smallest key, 2 for the second smallest, and so on.