Quicksort: Algorithm

Divide-and-Conquer Structure

Quicksort is a recursive divide-and-conquer sort:

1. Divide: Choose a pivot element from the array. Partition (rearrange) the array so that all elements $\le$ pivot come before it and all elements $\ge$ pivot come after it.
2. Conquer: Recursively sort the left and right subarrays (excluding the pivot, which is now in its correct final position).
3. Combine: Nothing to do — the pivot placement plus recursively sorted subarrays yields a fully sorted array.

Lomuto Partitioning

The standard partition scheme (Lomuto) picks the last element as pivot:

1. x = A[r] (pivot is last element)
2. i = p - 1 (boundary of ”$\le$ pivot” region)
3. For j = p to r-1:
4.  If A[j] <= x:
5.   i = i + 1
6.   Swap A[i] and A[j]
7. Swap A[i+1] and A[r] (place pivot in correct position)
8. Return i+1 (pivot’s index)

At any point, the array is partitioned as:

$[\, \underbrace{\text{elements} \le x}_{A[p \dots i]} \,|\, \underbrace{\text{elements} > x}_{A[i+1 \dots j-1]} \,|\, \underbrace{\text{unprocessed}}_{A[j \dots r-1]} \,|\, \underbrace{x}_{A[r]} \,]$

Walkthrough Example

Array: $[8, 2, 1, 5, 2, 4]$ with pivot $x = 4$

Step	j	Condition	Action	Result
Init	—	—	i = -1, pivot = 4	$[8, 2, 1, 5, 2, \underline{4}]$
1	0	$8 > 4$	Nothing	$[8, 2, 1, 5, 2, 4]$
2	1	$2 \le 4$	i=0, swap A[0],A[1]	$[2, 8, 1, 5, 2, 4]$
3	2	$1 \le 4$	i=1, swap A[1],A[2]	$[2, 1, 8, 5, 2, 4]$
4	3	$5 > 4$	Nothing	$[2, 1, 8, 5, 2, 4]$
5	4	$2 \le 4$	i=2, swap A[2],A[4]	$[2, 1, 2, 5, 8, 4]$
Final	—	—	swap A[3],A[5]	$[2, 1, 2, \underline{4}, 8, 5]$

Pivot 4 is at index 3. Left subarray $[2, 1, 2]$ and right subarray $[8, 5]$ are recursively sorted.

Hoare Partitioning (Alternative)

Hoare’s scheme uses two pointers moving inward from both ends, swapping out-of-order pairs. It typically performs fewer swaps than Lomuto, and the pivot ends up somewhere in the middle but not necessarily at the returned index.

Pivot Selection Strategies

Strategy	Effect
First element	Simple; worst case on sorted input
Last element	Simple; worst case on reverse-sorted input
Random	Expected $\Theta(n \log n)$; eliminates adversarial inputs
Median-of-three	Pivot is median of A[p], A[mid], A[r]; reduces worst-case probability
Median-of-medians	Guaranteed $\Theta(n \log n)$ worst case; high constant factor

The choice of pivot is the single most important factor affecting Quicksort’s performance. A poor pivot (extreme min or max) produces an $n-1$ to 1 split and degrades to $\Theta(n^2)$. A good pivot (median) gives balanced splits and $\Theta(n \log n)$.

Properties

Property	Value
In-place	Yes ($O(\log n)$ stack space for recursion)
Stable	No — partitioning swaps non-adjacent elements
Divide step	$\Theta(n)$ (one scan of subarray)
Combine step	No work required