What happened if we implement quicksort without tail recursion?

Question

On Wikipedia, it said that

The in-place version of quicksort has a space complexity of $\mathcal{O}(\log n)$, even in the worst case, when it is carefully implemented using the following strategies:

• in-place partitioning is used
• After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most $\mathcal{O}(\log n)$ space. Then the other partition is sorted using tail recursion or iteration, which doesn't add to the call stack.

Below is naive quick sort:

Quicksort(A, p, r)
{
 if (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  Quicksort(A, q+1, r)
 }
}

Below is tail recursion quick sort:

Quicksort(A, p, r)
{
 while (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  p: <- q+1
 }
}

Algorithms above are based on this link

What if we just use in place partitioning? Is it not enough to make quicksort having space complexity of $\mathcal{O}(\log n)$?

Below is what I understand of stack call of quicksort. Do I misunderstand it?

Suppose I have sequence of number: $\{3, 5, 2, 7, 4, 1, 8, 6\}$. I use in place method in this case.

input    : 5   3   2   7   4   1   8   6
partition: 3   2   4   1  (5)  7   8   6
stack 1  : 2   1  (3)  4
stack 2  : 1  (2)
stack 3  : 1                               - stack 3 removed
stack 2  : 1  (2)                          - stack 2 removed
stack 1  : 1   2  (3)   4
stack 2  :              4                  - stack 2 removed
stack 1  : 1   2  (3)   4                  - stack 1 removed
input    : 1   2   3   4  (5)  7   8   6
stack 1  :                    (6)  7   8
stack 2  :                        (7)  8
stack 3  :                             8   - stack 3 removed
stack 2  :                        (7)  8   - stack 2 removed
stack 1  :                    (6)  7   8   - stack 1 removed
input   : 1   2   3   4   5   6   7   8 -> sorted

We need $3$ stacks at most, which is $$\log(n) = \log(8) = 3$$

If what I told above is correct, the worst case with that method is $n$, which is happened when the pivot is the minimum or maximum

input    : 5   3   2   7   4   1   8   6
stack 1  :(1)  5   3   2   7   4   8   6
stack 2  :    (2)  5   3   7   4   8   6
stack 3  :        (3)  5   7   4   8   6
stack 4  :            (4)  5   7   8   6
stack 5  :                (5)  7   8   6
stack 6  :                    (6)  7   8
stack 7  :                        (7)  8
stack 8  :                             8
stack 7  :                        (7)  8
stack 6  :                    (6)  7   8
stack 5  :                (5)  6   7   8
stack 4  :            (4)  5   6   7   8
stack 3  :        (3)  4   5   6   7   8
stack 2  :    (2)  3   4   5   6   7   8
stack 1  :(1)  2   3   4   5   6   7   8
input    : 1   2   3   4   5   6   7   8 -> sorted

we need $8$ stacks, which is $n$

That's why in place partitioning is not enough. But if I am correct, what makes it different using tail recursion?

And also, anyone can give pseudo code for iteration instead of tail recursion?

Answer 1

You're correct that your version with a loop doesn't guarantee O(log n) additional memory. The problem is that you have recursively sorted the partition "on the left". You ignored:

the partition with the fewest elements is (recursively) sorted first

This is essential. It ensures that each time you make a recursive call (and lay down a new stack frame, requiring constant additional memory), the sub-array that you are sorting is at most half the size of sub-array being sorted at the previous stack level. Therefore the maximum depth of the recursion is the base-2 log n, which gives the desired bound on memory use.

In your code you permit a worst case in which you recursively sort the larger partition, having size only one smaller than the previous at each step. Then indeed the recursion depth can be n.

The way to make the code entirely iterative, with no call-recursion at all, is (as always) to use a stack data structure instead of the call stack. So instead of recursively calling to sort the small partition, you push the large partition on to the stack (by which I mean, push a pair of integers describing its location in the array) and loop around to continue sorting the small partition. When the size of the piece you're working on hits 1 you pop the stack and loop around to continue sorting that.

Answer 2

Below is an iteration-based quicksort proposed by Leslie Lamport. You can find it in this video lecture (title: Thinking for Programmers, from time: 32:35).

The basic idea is summarized as follows.

Initially, there is only an entire array. The first application of partition results in two subarrays. When the two subarrays are sorted separately and in place, the entire array is sorted. The second partition will divide one of the two subarrays into two smaller subarrays. Continuing on this, we obtain more and more subarrays with less and less elements to be sorted. Each of the smallest subarrays contains a single element and is sorted by default. In this way, we obtain an iterative quicksort algorithm.

Algorithm quick-sort-iter(A:array, lo:int, hi:int)
    @state
    range_array is an array (we use FIFO queue) of subarrays to be sorted; 
    each subarray is a triple of `(A, lo, hi)`.

  range_array := {(A, lo, hi)}

  while (range_array is not empty)
  {
    (A, lo', hi') := pop (and remove) a subarray from range_array
    if (lo' < hi')
    {
      p := partition(A, lo', hi)
      range_array := range_array + {(A, lo', p - 1), (A, p + 1, hi')}
    }
  }

Answer 3

No, it is not, because the recursive calls can go deeper than $log(n)$ in the worst case (they can atually go as deep as $O(n^2)$) and if you don't use tail-recursion then your computer needs to store the state at every level of recursion, because it will return to every level later. Tail reursion guarantees your computer that it does not need to store the data from every recursion level, because it will never get back to those levels anyway (as the recursive call should be exactly the last thing done in a tail-recursive method.)