Quicksort

Quicksort sorts by divide and conquer, but puts the work in the divide step. It chooses a pivot, partitions the array so that smaller elements come before larger ones, and then sorts the two parts recursively; no combine step is needed. It sorts in place, and its average running time is $\Theta(n \lg n)$ with small constants, which is why it is often the fastest sort in practice. Its worst case, however, is $\Theta(n^2)$, and the gap between the two cases is the centre of the analysis below.

Pseudocode uses 1-based arrays, <- for assignment and A[i..j] for the subarray from position $i$ to position $j$.

Initial call: QUICKSORT(A, 1, n). After PARTITION, the pivot is at its final sorted position $q$, every element of $A[p..q-1]$ is $\le A[q]$, and every element of $A[q+1..r]$ is $> A[q]$ (for the Lomuto scheme below).

The pivot is the last element $x = A[r]$.

Invariant at the start of each iteration: $A[p..i] \le x$, $A[i+1..j-1] > x$, $A[j..r-1]$ not yet examined, $A[r] = x$.

Trace on $A = [2, 8, 7, 1, 3, 5, 6, 4]$, pivot $x = 4$:

PARTITION returns $q = 4$. It makes exactly $r - p = 7$ key comparisons, $n - 1$ for a subarray of $n$ elements, on every input. It executes the exchange line 4 times (at $j = 1$, 4 and 5, plus the final one); if exchanges of an element with itself are not counted, that is 3. Questions that ask for "the number of swaps" usually intend one of these two conventions, so check which.

The pivot is the first element $x = A[p]$; two indices move towards each other and exchange out-of-place pairs.

With Hoare partition the recursive calls are QUICKSORT(A, p, j) and QUICKSORT(A, j + 1, r). It guarantees every element of $A[p..j]$ is $\le$ every element of $A[j+1..r]$, but the pivot is not necessarily at its final position, and $j$ is not the pivot's index.

Trace on $A = [5, 3, 8, 4, 9, 1, 6, 2, 7]$, $x = 5$: first $j$ stops at 8 ($A[8] = 2$) and $i$ at 1 ($A[1] = 5$); exchange to get 2 3 8 4 9 1 6 5 7. Next $j$ stops at 6 (value 1) and $i$ at 3 (value 8); exchange to get 2 3 1 4 9 8 6 5 7. Next $j$ stops at 4 (value 4) and $i$ at 5 (value 9); now $i > j$, so return $j = 4$. The parts are $[2, 3, 1, 4]$ and $[9, 8, 6, 5, 7]$; the pivot 5 sits inside the right part.

Hoare's scheme makes about three times fewer exchanges than Lomuto's on average and handles many equal keys far better, because both indices stop on keys equal to the pivot.

Let $T(n)$ be the time on $n$ elements. Partition costs $\Theta(n)$. If it produces parts of sizes $k$ and $n - 1 - k$:

The worst split is $0$ and $n - 1$ at every level: $T(n) = T(n-1) + \Theta(n) = \Theta(n^2)$. With the last-element pivot this happens on already sorted input, on reverse-sorted input, and (for Lomuto) on input where all keys are equal. The number of comparisons is then $(n-1) + (n-2) + \dots + 1 = n(n-1)/2$, and the recursion depth is $n - 1$.

For distinct keys, if every pivot is the median, $T(n) = 2T(n/2) + \Theta(n) = \Theta(n \lg n)$.

Even a persistently lopsided split such as 1 to 9 gives $T(n) = T(n/10) + T(9n/10) + \Theta(n)$. The recursion tree has full levels of cost at most $cn$ and depth $\log_{10/9} n = \Theta(\lg n)$, so $T(n) = \Theta(n \lg n)$. Only splits that are lopsided by a non-constant factor, such as a constant number of elements on one side, cause quadratic time.

For the shown Lomuto partition, assume distinct keys throughout this randomized analysis. Assume all $n!$ orderings of distinct keys are equally likely, or use randomized quicksort, which picks the pivot uniformly at random from $A[p..r]$ (exchange it with $A[r]$, then run PARTITION). Let $z_1 < z_2 < \dots < z_n$ be the keys in sorted order. Two keys are compared at most once, only when one of them is the first pivot chosen from $\{z_i, \ldots, z_j\}$, which happens with probability $2/(j - i + 1)$. Summing over all pairs,

where $H_n$ is the $n$-th harmonic number. For randomized quicksort this expectation holds for every input of distinct keys: no particular input is bad, only unlucky random choices are, and they are very unlikely.

Small cases make the formula concrete. For $n = 3$ it gives $8 \cdot \tfrac{11}{6} - 12 = \tfrac{8}{3}$, and for $n = 4$ it gives $10 \cdot \tfrac{25}{12} - 16 = \tfrac{29}{6}$; averaging Lomuto quicksort's comparison count over all 6 (or 24) input orders gives exactly these values. The pair probability is useful on its own: adjacent keys $z_i, z_{i+1}$ are always compared (probability $2/2 = 1$), since no key between them can separate them, while the smallest and largest keys are compared with probability only $2/n$ (one of them must be the very first pivot).

Quicksort uses $O(1)$ auxiliary space besides the recursion stack, so it is called in place. The stack depth is $\Theta(\lg n)$ on balanced splits but $\Theta(n)$ in the worst case. Recursing on the smaller part first and looping on the larger (tail-call elimination) bounds the depth by $O(\lg n)$ in every case.

Related material. Selection is not a separate item of the GATE syllabus. It is included because it reuses PARTITION and is commonly studied together with quicksort.

The same partition finds the $k$-th smallest element without sorting: partition, then recurse into one side only.

For distinct keys, the displayed Lomuto-based Quickselect has expected time $\Theta(n)$ (the expected sizes shrink geometrically) and worst case $\Theta(n^2)$. The median-of-medians pivot rule (groups of 5) gives worst-case $\Theta(n)$ under the same distinct-key condition. To retain these linear guarantees with duplicate keys, use a three-way partition and return immediately when k lies in the equal block (CLRS 3e, Section 9.3).

Quickselect time and workspace. Here $n=r-p+1\ge1$, comparisons, swaps and random-index generation are constant-time, and each pivot is chosen uniformly in the current subarray. Best time is $\Theta(n)$, when the first partition finds the target. Without tail-call elimination, the displayed one-subproblem recursion has $\Theta(1)$ best call-stack space, $O(\lg(n+1))$ expected space and $\Theta(n)$ worst space, with constant-size frames and no copied subarrays; input storage and the scalar result are excluded. Replacing the single recursive call by a loop gives $O(1)$ auxiliary words with the same time bounds. These randomized stack bounds do not analyze the median-of-medians pivot subroutine; a straightforward implementation that copies medians into separate arrays uses $O(n)$ auxiliary words including its stack.