This quicksort example uses the Lomuto partition scheme, with the last element as the pivot and 0-based inclusive bounds. It shows the exact quicksort pseudocode, a complete partition trace, and the recursive calls needed to sort an array in place.

At each call, partition places the pivot in its final position. Quicksort then processes the elements to its left and right. A range containing zero or one element is already sorted.

Quicksort Example: The Divide-and-Conquer Plan

For a range A[low..high], choose a pivot and rearrange the range so values on one side are less than or equal to it, while values on the other side are greater. The partition function returns the pivot’s final index, p.

The recursive calls use low..p-1 and p+1..high. The pivot is excluded from both calls because it is already in the correct position.

This implementation uses Lomuto consistently: the pivot is A[high], the scan index j runs from low through high-1, and i marks the next position for a value less than or equal to the pivot.

Quicksort Pseudocode with Lomuto Partition

Use inclusive, 0-based indices. The base condition low >= high stops recursion.

QUICKSORT(A, low, high)

1. If low < high, set p = PARTITION(A, low, high).
2. Call QUICKSORT(A, low, p – 1).
3. Call QUICKSORT(A, p + 1, high).

PARTITION(A, low, high)

1. Set pivot = A[high].
2. Set i = low.
3. For each j from low to high-1, if A[j] <= pivot, swap A[i] and A[j], then increase i by one.
4. Swap A[i] and A[high].
5. Return i.

After partitioning, every element before index i is less than or equal to the pivot, and every element between i+1 and high is greater. The returned index is therefore the boundary for the two recursive ranges.

Partition Trace: Array Changes and Recursive Bounds

Trace A = [9, 4, 7, 3, 10, 5] with QUICKSORT(A, 0, 5). Lomuto selects 5, the final element, as the pivot.

• j = 0: 9 is greater than 5, so no swap occurs. The array remains [9, 4, 7, 3, 10, 5].
• j = 1: 4 qualifies. Swap positions 0 and 1: [4, 9, 7, 3, 10, 5]. Now i = 1.
• j = 2: 7 is greater than 5, so the array is unchanged.
• j = 3: 3 qualifies. Swap positions 1 and 3: [4, 3, 7, 9, 10, 5]. Now i = 2.
• j = 4: 10 is greater than 5, so the array is unchanged.
• Final swap: Swap A[2] and A[5]: [4, 3, 5, 9, 10, 7]. Partition returns p = 2.

The next bounds are QUICKSORT(A, 0, 1) and QUICKSORT(A, 3, 5). The left call uses pivot 3, producing [3, 4, 5, 9, 10, 7] and p = 0; its subcalls are (0, -1) and (1, 1), both finished ranges.

The right call uses pivot 7, producing [3, 4, 5, 7, 10, 9] and p = 3. Its right range (4, 5) uses pivot 9, producing [3, 4, 5, 7, 9, 10] and p = 4. The remaining bounds, (3, 2), (4, 3), and (5, 5), meet the base condition.

Time, Space, and Pivot Choice in Quicksort

Each partition scans its current range once. With reasonably balanced splits, the recurrence is T(n) = 2T(n/2) + O(n), giving average or expected time of O(n log n). If the pivot is repeatedly the smallest or largest value, the recurrence becomes T(n) = T(n-1) + O(n), producing worst-case time of O(n²). A sorted array and a last-element pivot can create this worst case.

Lomuto rearranges the array in place, requiring O(1) auxiliary storage apart from the recursion stack. Stack space averages O(log n) with balanced splits and can reach O(n) in the worst case. Randomized pivots or median-of-three selection reduce imbalance; move the selected pivot to A[high] before applying the same Lomuto rules.