Quicksort - which sub-part should be sorted first?

Question

I am reading some text which claims this regarding the ordering of the two recursive Quicksort calls:

... it is important to call the smaller subproblem first, this in conjunction with tail recursion ensures that the stack depth is log n.

I am not at all sure what that means, why should I call Quicksort on the smaller subarray first?

Answer 1

Look at quicksort as an implicit binary tree. The pivot is the root, and the left and right subtrees are the partitions you create.

Now consider doing a depth first search of this tree. The recursive calls actually correspond to doing a depth first search on the implicit tree described above. Also assume that the tree always has the smaller sub-tree as the left child, so the suggestion is in fact to do a pre-order on this tree.

Now suppose you implement the preorder using a stack, where you push only the left child (but keep the parent on the stack) and when the time comes to push the right child (say you maintained a state where you knew whether a node has its left child explored or not), you replace the top of stack, instead of pushing the right child (this corresponds to the tail recursion part).

The maximum stack depth is the maximum 'left depth': i.e. if you mark each edge going to a left child as 1, and going to a right child as 0, then you are looking at the path with maximum sum of edges (basically you don't count the right edges).

Now since the left sub-tree has no more than half the elements, each time you go left (i.e. traverse and edge marked 1), you are reducing the number of nodes left to explore by at least half.

Thus the maximum number of edges marked 1 that you see, is no more than log n.

Thus the stack usage is no more than log n, if you always pick the smaller partition, and use tail recursion.