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?