Quick Sort —
Pick a pivot, partition around it, recurse.
Quick sort picks one element as a pivot, moves everything smaller to its left and everything larger to its right, then recursively sorts each side — no merging step needed, because once partitioning finishes, the pivot is already in its final position. Watch the partition happen element by element on LearnBug and see why pivot choice matters so much.
What is Quick Sort?
Choose a pivot element, then partition the rest of the array into two groups: everything ≤ pivot, and everything > pivot. Once partitioned, the pivot sits exactly where it belongs in the final sorted order — no further work needed on it. Recursively quick-sort each side, and the whole array ends up sorted.
Why visualization helps
The partition step is the part everyone finds slippery — which elements move where, and why the pivot's position doesn't need to change again afterward. LearnBug highlights the pivot and shows each comparison decide "left group" or "right group" live, so the partition result stops feeling like magic.
Why the "average case" and "worst case" are so far apart
Good pivot → roughly even split
If the pivot lands near the middle value, each recursive call handles about half the remaining elements — the same log n depth as merge sort.
Bad pivot → nearly no split at all
Picking the smallest or largest element as pivot (e.g. always the last element on already-sorted input) puts everything on one side — the recursion barely shrinks per call.
Random or median-of-three pivots defend against this
Picking a random element, or the median of the first/middle/last elements, makes the worst case extremely unlikely in practice, even though it's still theoretically possible.
Sorting [8, 3, 5, 1, 9, 2] — last element as pivot
Pivot = 2 (last element). Partition [8, 3, 5, 1, 9] around it
Every element except the pivot is compared to 2. Since 2 is the smallest of the remaining elements, everything except 1 ends up larger than it.
≤2: [1]. >2: [8, 3, 5, 9]. Pivot 2 slots between them — its final position
Only 1 is ≤ the pivot. Everything else — 8, 3, 5, 9 — is greater. The pivot now sits at index 1 in the array, which is exactly where it belongs in the fully sorted result.
Quick sort the right group [8, 3, 5, 9] — new pivot = 9 (last element)
[1] is already sorted (single element, base case). The right group recurses independently: pivot 9, everything else (8, 3, 5) is ≤ 9, so it all lands on the left.
[8, 3, 5] recurses similarly — pivot 5, then pivot 8 — everything falls into place
Pivot 5 splits [8,3,5] into [3] and [8], with 5 between them → [3,5,8]. Combining all pieces: [1] + [2] + [3,5,8] + [9].
Return: [1, 2, 3, 5, 8, 9] ✓ each pivot found its final position without ever moving again
Partition, then recurse
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[-1] # last element as pivot
left = [x for x in arr[:-1] if x <= pivot] # everything smaller or equal
right = [x for x in arr[:-1] if x > pivot] # everything larger
return quick_sort(left) + [pivot] + quick_sort(right)
print(quick_sort([8, 3, 5, 1, 9, 2]))Complexity Notes
Frequently asked questions
Why is quick sort's worst case O(n²) if merge sort is always O(n log n)?
Quick sort's split depends entirely on how good the pivot choice is — a bad pivot (like always picking the smallest or largest remaining element) puts nearly all elements on one side, so the recursion barely shrinks and you get roughly n levels instead of log n. Merge sort's split is always exactly in half by index, with no dependence on the data at all, so it can't degrade this way.
Why is last-element-as-pivot risky?
On already-sorted (or reverse-sorted) input, the last element is always the maximum (or minimum) of the remaining array — the worst possible pivot, since it produces a completely lopsided partition every single time. Random pivot selection or median-of-three avoids this specific, common failure pattern.
Why does quick sort often beat merge sort in practice despite the worse worst case?
Quick sort (done in-place with swaps, not list comprehensions) has better cache locality and lower constant-factor overhead — it doesn't need to allocate new arrays the way merge sort's merge step does. For typical real-world data with a good pivot strategy, the O(n²) worst case is rare enough that the average-case speed wins.
Does the pivot ever need to move again after partitioning?
No — that's the key property that makes quick sort not need a separate merge step. Once partitioning finishes, everything smaller is to the pivot's left and everything larger is to its right, which is exactly where it belongs in the final sorted array. Only the two sides still need sorting, not the pivot itself.
Watch the partition happen, element by element
Paste quick sort into LearnBug and see every comparison decide left or right of the pivot.