# Analysis of Tail Recursive Quicksort

**Publish date:**Aug 3, 2017

This is a problem that appears as a practice question in Introduction to Algorithms 2rd edition, 3rd Edition by Charles E. Leiserson, Clifford Stein, Ronald Rivest, and Thomas H. Cormen. It’s also an interesting exercise / excuse to dig far too deep into quicksort!

## Pseudocode

```
def tailRecursiveQuickSort(A, startIdx, endIdx):
while startIdx < endIdx:
pivotIdx = PARTITION(A, startIdx, endIdx)
tailRecursiveQuickSort(A, startIdx, pivotIdx - 1)
startIdx = pivotIdx + 1
```

## Analysis

In the first iteration of `tailRecursiveQuickSort`

, the left subarray gets processed i.e. the first call is $\textbf{tailRecursiveQuickSort}(A, 1, q-1)$

After this the p value changes to $p_{2} = q + 1$ which is the p-value for the second iteration which makes the call $\textbf{tailRecursiveQuickSort}(A, p_{2}, q_{2}-1)$ where $q_{2} = \textbf{PARTITION}(A, p_{2}, r)$.

This can be generalized to the $i^{th}$ iteration as follows:

- Function call made: $\textbf{tailRecursiveQuickSort}(A, q_{i-1} + 1, q_{i} - 1),$
- $p_{i} = q_{i-1} + 1,$
- $q_{i} = \textbf{PARTITION}(A, q_{i-1} + 1, r)$

Observe that: $q_{i-1} + 1 \leq q_{i} \leq r$. Thus during each iteration, $q$ is guaranteed to be incremented by at least $1$.

Additionally, by the $i^{th}$ iteration, the following recursive calls have been excuted on disjoint subarrays of $A$

- $\textbf{tailRecursiveQuickSort}(A, p_{1}, q_{1} - 1)$ where $p_{1} = 1, q_{1} = q$
- $\textbf{tailRecursiveQuickSort}(A, q_{1} + 1, q_{2} - 1)$
- $\vdots$
- $\textbf{tailRecursiveQuickSort}(A, q_{i-1} + 1, q_{i} - 1)$

Since each of these calls acts on a disjoint sub-array with intermediate calls to `PARTIION`

which guarantees that each $q_{i}$ is in it’s correct place; these calls can be group together to be seen as a single call to `tailRecursiveQuickSort`

which performs the divide.

Therefore calls from $(b)$ through $(c)$ above can be grouped into: $\textbf{tailRecursiveQuickSort}(A, q+1, q_{i}-1)$ at the end of the $i^{th}$ iteration.

Since $q_{i}$ is guaranteed to increase every by atleast $1$ every iteration, so is $p_{i} = q_{i} + 1$. This implies that the while loop must terminate for some value of $p_{i} > r$, which is guaranteed due to its strictly increasing behavior. Therefore the sequence $q_{i}$ must eventually cross $r$ for some $i = k$ such that $q_{k} \geq r$.

So the sequence of calls from the second iteration onwards can be rewritten as the following net result: $\textbf{tailRecursiveQuickSort}(A, q+1, r)$. Therefore the original `tailRecursiveQuickSort`

function can be rewritten as follows (after fully unrolling the while loop)

```
def tailRecursiveQuickSort(A, startIdx, endIdx):
pivotIdx = PARTITION(A, startIdx,
tailRecursiveQuickSort(A, startIdx, pivotIdx - 1)
tailRecursiveQuickSort(A, endIdx, pivotIdx + 1)
```

## Conculsion

The last bit of pseudocode we made by transforming the original code is exactly the same as `QUICKSORT`

therefore, `tailRecursiveQuickSort`

and `QUICKSORT`

are functionally equivalent, proving that `tailRecursiveQuickSort`

is able to sort any input sequence, given the correctness of the `PARTITION`

routine.

Alternatively, one can also say that the correctness, convergence of `QUICKSORT`

guarantees the correctness of this tail recursive form.