The Story That Makes Quicksort Click
Now you have two smaller crowds. You repeat the same trick inside each group: pick a pivot, split left and right, lock the pivot in. Keep going on ever-smaller groups until every group has one person — and the whole line is sorted.
That is Quicksort: partition around a pivot, then recursively quicksort the two halves. Divide, conquer, done.
Quicksort is a divide-and-conquer algorithm. Each partition step picks a pivot and rearranges the current section so that everything smaller sits to its left and everything larger to its right. The pivot then lands in its final position, and the algorithm recurses on the left and right sections independently.
One partition pass does not sort the section — it just guarantees the pivot is home and cleanly separates "smaller" from "larger." That single guarantee, applied recursively, is enough to sort everything in O(n log n) on average, fully in place, which is why quicksort is the fastest general-purpose sort in practice.
Divide and Conquer — One Pivot, Two Sub-Problems
Every partition turns one problem into two smaller, independent ones. The pivot is removed from play (it is already final), and quicksort is called again on each side.
Unlike Merge Sort, quicksort does its splitting by swapping elements within the same array — no auxiliary array needed. Only the recursion call stack uses extra space (O(log n) on average). That, plus excellent CPU-cache behaviour, is why quicksort usually beats merge sort and heapsort on real hardware.
The Partition Step (Lomuto Scheme)
The animation below uses the Lomuto partition: the pivot is the last element,
a boundary pointer i marks the end of the "smaller than pivot" zone, and a scanner
j walks across the section.
i = low - 1 (the smaller-zone is empty).
j from low to high - 1. Compare each element to the pivot.
arr[j] < pivot, grow the smaller-zone: i += 1, then swap arr[i] with arr[j].
i + 1 — right after the smaller-zone. That index is its final home.
Hands-On: Watch Every Line of Code Execute
Press Play (or step manually). The highlighted Python line
moves in lock-step with the animated array. The amber i and blue
j pointers track the partition; the purple bar is the pivot; the active recursion
window stays bright while inactive sub-sections dim. Each time a pivot locks into place it turns
green permanently. Use Shuffle for a fresh array.
The blue j sweeps the window comparing each value to the purple pivot. Whenever a
value is smaller, the amber i advances and a red swap pulls that value into the
growing "< pivot" zone (the amber-underlined bars). At the end of the scan, the pivot swaps
to just past that zone and turns green. Then quicksort dives into the left window, then the
right.
The Full Python Implementation
def partition(arr, low, high):
pivot = arr[high] # choose the last element as pivot
i = low - 1 # end of the "< pivot" zone
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i] # move smaller value left
arr[i + 1], arr[high] = arr[high], arr[i + 1] # pivot into place
return i + 1
def quick_sort(arr, low, high):
if low < high:
p = partition(arr, low, high)
quick_sort(arr, low, p - 1) # sort left of pivot
quick_sort(arr, p + 1, high) # sort right of pivot
return arr
# --- driver ---
data = [5, 3, 8, 1, 9, 2, 7]
print("Before:", data)
quick_sort(data, 0, len(data) - 1)
print("After: ", data)A Verbose Version That Shows Each Pivot Landing
def quick_sort_verbose(arr, low, high):
if low < high:
p = partition(arr, low, high)
print(f"pivot {arr[p]:>2} -> final index {p} {arr}")
quick_sort_verbose(arr, low, p - 1)
quick_sort_verbose(arr, p + 1, high)
return arr
quick_sort_verbose([5, 3, 8, 1, 9, 2, 7], 0, 6)The first pivot (7) lands at index 4, splitting the work. Quicksort then fully sorts the left window before touching the right — that is the recursion unfolding depth-first. Each printed line is one pivot reaching its permanent home.
Why Use Quicksort? The Real Benefits
std::sort, introsort, and dual-pivot quicksort in Java.
Most standard-library sorts are quicksort-based hybrids. Introsort runs quicksort but watches the recursion depth; if a bad pivot streak threatens O(n²), it switches to heapsort to guarantee O(n log n), and uses insertion sort for tiny sub-arrays. Best of all worlds.
When to Use It — and When Not To
Time & Space Complexity
| Case | When It Happens | Time | Space (stack) |
|---|---|---|---|
| Best | Pivot splits the section evenly | O(n log n) | O(log n) |
| Average | Random data, reasonable pivots | O(n log n) | O(log n) |
| Worst | Pivot is always min/max (e.g. sorted input, last-element pivot) | O(n²) | O(n) |
| Stable? | Far-apart swaps reorder equal keys | No (not stable) | |
If every pivot is the smallest or largest element, each partition peels off just one element and the recursion becomes n levels deep — that is the O(n²) trap, and ironically it hits already-sorted input when you always pick the last element. A random or median-of-three pivot makes this practically impossible.
Choosing a Good Pivot
Quicksort vs Its Cousins
| Property | Quicksort | Merge Sort | Heapsort | Insertion Sort |
|---|---|---|---|---|
| Average | O(n log n) | O(n log n) | O(n log n) | O(n²) |
| Worst case | O(n²) | O(n log n) | O(n log n) | O(n²) |
| Extra space | O(log n) | O(n) | O(1) | O(1) |
| Stable? | No | Yes | No | Yes |
| In practice | Usually fastest | Fast, needs memory | Slower (cache misses) | Great when tiny |
| Best for… | General-purpose speed | Stable / linked lists | Worst-case + low memory | Small / nearly-sorted |
Reach for quicksort as your default for sorting large in-memory arrays where stability is not required — just use a randomised or median-of-three pivot. When you need a guaranteed bound, stability, or are sorting linked/external data, switch to heapsort or merge sort instead.
Golden Rules
i is the boundary of the smaller-zone and j is the scanner.
The pivot ends at i + 1 after the loop — never forget that final swap.
low < high. Sections of size 0 or 1 are already sorted, so the
recursion simply stops there.