# Sorting in computing longest increasing subsequence

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?

• 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)$$.