Sorting in computing longest increasing subsequence
Here is a sketch of the proof of Theorem 3.5:

If there is a comparison-based algorithm for LIS using $m$ comparisons in the worst case, then we can convert it to an algorithm which answers the question &quot;is $L \geq k$&quot; (for some fixed $k$) using $m$ comparisons.
Given an algorithm which answers the question &quot;is $L \geq k$&quot; using $m$ comparisons, we can convert it into an algorithm using $m + n \log k + O(n)$ comparisons which sorts the input whenever $L &lt; k$.
Any comparison-based algorithm which sorts the input whenever $L &lt; k$ must perform at least $\log S(n,k)$ comparisons (since it has at $S(n,k)$ possible outputs).
Consequently, every comparison-based algorithm for LIS must use at least $\log S(n,k) - n \log k - O(n)$ comparisons.
The theorem follows by choosing $k = \lfloor 3\sqrt{n} \rfloor$ and using the asymptotics of $S(n,k)$.

We sort the input in order to use a lower bound on sorting.