# Inductive proof on Quicksort with Explicit Stacking

Prove by induction that if Quicksort with Explicit Stacking is modified so that the end-points of the larger sublist are stacked, and the other sublist is sorted first, then the maximum stack size is $$O(\lg n)$$.

This is because the smaller sublist has length $$\le 1/2$$ the length of the current list. But how can this be proved using induction?