Quick Sort: Partition Around a Pivot

The Problem#

Given an unsorted array of integers, sort it in ascending order as efficiently as possible.

---

The Core Concept: Partition#

Quick Sort uses divide and conquer. It picks one element as the pivot and rearranges the array so that:

• Every element to the left of the pivot is smaller.
• Every element to the right of the pivot is larger.

After partitioning, the pivot is in its final sorted position. Recursively applying this to both halves sorts the entire array.

---

The Partition Step (Lomuto Scheme)#

Using the last element as pivot on [3, 6, 8, 10, 1, 2, 1], pivot = 1:

1. Walk through left to right with pointer i.
2. Whenever arr[j] <= pivot, increment i and swap arr[i] with arr[j].
3. Finally, place pivot at i + 1.

After one partition: [1, 1, 8, 10, 3, 2, 6] → pivot 1 is now in place at index 1.

---

Code Implementation#

• Time Complexity: O(N log N) average; O(N²) worst case (already-sorted array with last-element pivot).
• Space Complexity: O(log N) stack space for recursion.

---

Interactive Lab: Quick Sort#

Let's take the example in the visualization below: [5, 2, 8, 1, 9, 3, 10, 4, 6, 7]. The red pivot chip is the one to follow. It parks on the last element for the whole scan, then hops to its final resting index at the very end of the partition.

Step through just the first partition:

• The pivot is 7, the last element. The j chip sweeps left to right; the decision panel announces each comparison against 7 and whether it triggers a swap.
• Everything smaller than 7 gets herded to the front. When j reaches the end, the array reads [5, 2, 1, 3, 4, 6, | 10, 9, 8, | 7] and the pivot swaps into the boundary slot.
• Result: [5, 2, 1, 3, 4, 6, 7, 9, 8, 10]. 7 is now at index 6 for good. It will never be touched again, even though nothing around it is sorted yet.

That last line is the property to internalize. One partition pass buys you exactly one element in its final position, plus the guarantee that the six bars on its left and the three on its right can now be sorted independently, which is exactly what the recursion does next, first on [5, 2, 1, 3, 4, 6] and then on [9, 8, 10].

---

Quick Sort vs Merge Sort#

	Quick Sort	Merge Sort
Average	O(N log N)	O(N log N)
Worst	O(N²)	O(N log N)
Space	O(log N)	O(N)
Stable	No	Yes
Cache	Excellent	Good

Quick Sort wins in practice due to superior cache locality and lower constant factors, despite the theoretically worse worst case. Most standard library sort implementations (like introsort in C++) use Quick Sort as their base.