Previously, the Quicksort implementation was written in the obvious
way: after each partitioning step, it explicitly recursed twice to
sort the two sublists. Now it compares the two sublists' sizes, and
recurses only to sort the smaller one. To handle the larger list it
loops back round to the top of the function, so as to handle it within
the existing stack frame.
This means that every recursive call is handling a list at most half
that of its caller. So the maximum recursive call depth is O(lg N).
Otherwise, in Quicksort's bad cases where each partition step peels
off a small constant number of array elements, the stack usage could
grow linearly with the array being sorted, i.e. it might be Θ(N).
I tested this code by manually constructing a List Of Doom that causes
this particular quicksort implementation to hit its worst case, and
confirming that it recursed very deeply in the old code and doesn't in
the new code. But I haven't added that list to the test suite, because
the List Of Doom has to be constructed in a way based on every detail
of the quicksort algorithm (pivot choice and partitioning strategy),
so it would silently stop being a useful regression test as soon as
any detail changed.