What Is Quick Sort?
Quick Sort is a divide-and-conquer algorithm that picks one pivot, sends smaller values to its left and larger ones to its right, then sorts each side the same way. Like merge sort it averages O(n log n), but it sorts in place with almost no extra memory.
The one-line idea: "put the pivot where it belongs." After a single partition, the pivot sits exactly at its final sorted position.
The Heart Is Partitioning
Almost all the work happens in the partition step.
1. Pick one element of the range as the pivot (here, the last value).
2. Scan the range, gathering values smaller than the pivot toward the front.
3. Finally move the pivot to that boundary, so everything left of the pivot is smaller and everything right is larger.
The pivot is now done. Repeat the same partition independently on the left and right sub-ranges and the whole array becomes sorted.
How It Works
Step 1. For the range [lo, hi], let pivot = arr[hi].
Step 2. Keep a boundary index i = lo. Move j from lo to hi-1; whenever arr[j] < pivot, swap arr[i] with arr[j] and increment i.
Step 3. After the scan, swap arr[i] with arr[hi] (the pivot). The pivot is now fixed at index i.
Step 4. Recurse on [lo, i-1] and [i+1, hi]. Stop when a range has one or zero elements.
"Compare" and "swap" are distinct actions, and the AlgoNote visualization shows each as its own step.
Time and Space Complexity
| Complexity | |
|---|---|
| Time (average) | O(n log n) |
| Time (worst) | O(n²) |
| Space | O(log n) |
On average, partitions split roughly in half, giving depth log n with n comparisons per level → O(n log n). But if you always pick the last element as pivot on an already-sorted array, one side stays empty, depth grows to n, and it becomes O(n²). Space is just the recursion stack (O(log n)); no large auxiliary array is used.
Walking Through an Example
For arr = [5, 2, 8, 1, 4], take the last value 4 as the pivot.
- •j=0: 5 < 4? no
- •j=1: 2 < 4? yes → swap with arr[0] →
[2, 5, 8, 1, 4], i=1 - •j=2: 8 < 4? no
- •j=3: 1 < 4? yes → swap with arr[1] →
[2, 1, 8, 5, 4], i=2 - •Finally swap arr[2] with the pivot →
[2, 1, 4, 5, 8]
The pivot 4 is fixed at index 2; sort the left [2, 1] and right [5, 8] and you're done.
Common Mistakes
- •Pivot choice: always taking the last element is O(n²) on sorted input. Mitigate with a random pivot or median-of-three.
- •Comparison operator: getting
arr[j] < pivotwrong skews partitions to one side when there are many duplicates, hurting performance. - •Termination: only partition when
lo < hi; a range with one or zero elements is already sorted.
See It in Action on AlgoNote
Watch how the pivot is chosen, smaller values gather to the front, and the pivot lands in its final spot, step by step on AlgoNote.