algorithm - quicksort stack size

Question

Why do we prefer to sort the smaller partition of a file and push the larger one on stack after partitioning for quicksort(non-recursive implementation)? Doing this reduces the space complexity of quicksort O(log n) for random files. Could someone elaborate it?

Answer 1

As you know, at each recursive step, you partition an array. Push the larger part on the stack, continue working on the smaller part.

Because the one you carry on working with is the smaller one, it is at most half the size of the one you were working with before. So for each range we push on the stack, we halve the size of the range we're working with.

That means we can't push more than log n ranges onto the stack before the range we're working with hits size 1 (and therefore is sorted). This bounds the amount of stack we need to complete the first descent.

When we start processing the "big parts", each "big part" B(k) is bigger than the "small part" S(k) produced at the same time, so we might need more stack to handle B(k) than we needed to handle S(k). But B(k) is still smaller than the previous "small part", S(k-1) and once we're processing B(k), we've taken it back off the stack, which therefore is one item smaller than when we processed S(k), and the same size as when we processed S(k-1). So we still have our bound.

Suppose we did it the other way around - push the small part and continue working with the large part. Then in the pathologically nasty case, we'd push a size 1 range on the stack each time, and continue working with a size only 2 smaller than the previous size. Hence we'd need n / 2 slots in our stack.