Quicksort in log space [Solution]

The problem was to implement in-place quicksort (partitioning by pivoting on first element) in worst case $O(\log n)$ space.

Solution

---

This is a classic, probably due to Robert Sedgewick.

The absolutely trivial implementation of quicksort looks like

def qsort(arr, L, R):
  if L >= R:
    return
  mid = partition(arr)
  qsort(arr, L, mid)
  qsort(arr, mid+1, R)

Now the two recursive calls are interchangeable and the last one can be made tail recursive.

If we always pick the smaller partition to recurse on, and tail recurse on the larger partition, we will end up only using $O(\log n)$ space!

An implementation might look like (handwaving here)

def qsort(arr, L, R):
  while R > L:
  mid = partition(arr)
  if mid -L < R - mid:
    qsort(arr, L, mid)
    L,R = mid, R
   else:
    qsort(mid, R)
    L,R = L, mid

Note this idea can be used to make recursive binary tree traversals use $O(\log n)$ space, irrespective  of the tree structure, as long we maintain a count of the descendants of each node: recurse on the smaller tree, but tail recurse on the larger one.