Sorting in computing longest increasing subsequence

Question

I am currently reading the paper On computing the length of longest increasing subsequences by Michael L. Fredman.

I'm struggling to understand parts of the proof of Theorem 3.5,
especially this bit:

Now consider the following enhancement $A^*$ of $A$. Whenever $A$ concludes that $L < k$, $A^*$ continues to completely sort $S$ [...]

This is used to show a bound for $L \ge k$, but why are they sorting the sequence?

Answer 1

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 "is $L \geq k$" (for some fixed $k$) using $m$ comparisons.
• Given an algorithm which answers the question "is $L \geq k$" using $m$ comparisons, we can convert it into an algorithm using $m + n \log k + O(n)$ comparisons which sorts the input whenever $L < k$.
• Any comparison-based algorithm which sorts the input whenever $L < 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.