A high-efficiency "Divide and Conquer" algorithm that partitions data around a pivot to sort recursively.
Parameters
12
Visualization
Step: 0
Click Randomize or Step to start partitioning.
Algorithm Insight
Quick Sort partitions the array around a Pivot element.
1.Select a pivot (often the last element).
2.Move elements smaller than pivot to the left.
3.Move larger elements to the right.
4.Recursively repeat for left and right sub-ranges.
Complexity
Average CaseO(N log N)
Space ComplexityO(log N)
Overview
Quicksort partitions an array around a pivot, placing smaller values on one side and larger values on the other, then sorts each side recursively. Its average running time is O(n log n), but poor pivot choices can produce O(n²) work.
Work one through by hand
Sort [7, 2, 9, 4, 1, 8] using the last element, 8, as pivot.
less than 8: [7, 2, 4, 1] | pivot: 8 | greater: [9]
8 is now final at index 4. Recurse left on [7, 2, 4, 1] with pivot 1:
less: [] | pivot: 1 | greater: [7, 2, 4]
Then [7, 2, 4] with pivot 4 gives [2] | 4 | [7], placing the pivot in its final position. This partition is balanced; an earlier split with 0 elements on one side and 3 on the other illustrates the unbalanced case that can lead to quadratic work.
Best case, worst case, and why the average holds
When the pivot lands near the median, each partition halves the array, giving log n levels of O(n) partitioning work: O(n log n).
When the pivot is consistently the smallest or largest element, one side gets n−1 elements and the other gets none. That gives n levels of O(n) work: O(n²). With a fixed first- or last-element pivot, already-sorted input is one example that causes this behavior.
With randomized pivot selection, the expected running time is O(n log n) for a fixed input, though the worst case remains quadratic. A 90/10 split at every level is still logarithmic in depth, with a larger constant than balanced partitions.
Exploration guide
Watch a pivot settle permanently. Set Array Size to 15 and press Next Step through one partition. When it completes, the pivot is in its final position and is never moved again. Unlike merge sort, elements finish one at a time.
Find a bad split. Press Randomize Array and Auto-Run a few times, watching the partition sizes. Sometimes one side gets almost all of it; that single unbalanced level is a small dose of the worst case.
Why it beats merge sort in practice
Both are O(n log n) on average, yet quick sort is usually faster on arrays. Three reasons:
No auxiliary array. Partitioning is in-place. The recursive stack is O(log n) on balanced partitions but can grow to O(n) in the worst case. Merge sort needs an O(n) buffer.
Cache behaviour. Partitioning sweeps two pointers inward through contiguous memory. This is close to the ideal access pattern for a CPU prefetcher.
Smaller constant factor. The inner loop is a comparison and a conditional swap, with no writes to a second array and no copy-back.
Production implementations use safeguards. Random pivots reduce dependence on input order; median-of-three helps on common patterns but is not a worst-case guarantee. Introsort, used by C++ std::sort, switches to heapsort when recursion gets too deep, preserving an O(n log n) worst-case bound.
Common mistakes with Quick Sort
Always taking the first or last element as pivot. This makes already-sorted input the worst case. This is the input you are most likely to receive. Use median-of-three or a random pivot.
Mishandling duplicates. An array of all-equal elements sends every element to one side under naive partitioning, giving O(n²). Three-way (Dutch national flag) partitioning splits into less / equal / greater and handles it in linear time.
Recursing on the larger side first. Recursing into the smaller partition and looping on the larger caps stack depth at O(log n). Doing it the other way risks stack overflow on adversarial input.
Expecting stability. Quick sort is not stable — partitioning swaps distant elements and reorders equal keys. If you need stability, use merge sort.
Continue with merge sort, which builds on this idea.
Run it in Python
Lomuto partitioning, printed at each level, followed by the case everyone warns about: a sorted input with a last-element pivot, counted to show the recursion depth going linear.
quick_sort.pyPython 3
# Quicksort: partition around a pivot, then sort the two sides.
import sys
def partition(a, lo, hi):
pivot = a[hi] # Lomuto: the last item is the pivot
i = lo - 1 # end of the "smaller than pivot" region
for j in range(lo, hi):
if a[j] <= pivot:
i += 1
a[i], a[j] = a[j], a[i]
a[i + 1], a[hi] = a[hi], a[i + 1] # drop the pivot into its final place
return i + 1
def quicksort(a, lo=0, hi=None, depth=0, stats=None, show=True):
if hi is None:
hi = len(a) - 1
if stats is not None:
stats["depth"] = max(stats["depth"], depth)
stats["calls"] += 1
if lo >= hi:
return
p = partition(a, lo, hi)
if show:
print(f"{' ' * depth}pivot {a[p]:>3} -> {a[lo:p]} [{a[p]}] {a[p+1:hi+1]}")
quicksort(a, lo, p - 1, depth + 1, stats, show)
quicksort(a, p + 1, hi, depth + 1, stats, show)
data = [10, 80, 30, 90, 40, 50, 70]
print("start :", data)
quicksort(data)
print("sorted:", data)
print()
sys.setrecursionlimit(10000)
for name, sample in [("random", [5, 2, 8, 1, 9, 3, 7, 4, 6]),
("already sorted", list(range(1, 10)))]:
stats = {"depth": 0, "calls": 0}
quicksort(sample[:], stats=stats, show=False)
print(f"{name:>15}: depth {stats['depth']:>2}, {stats['calls']} calls")
print()
print("Sorted input is quicksort's worst case, not its best.")
Output
How the code works
pivot = a[hi]The choice that decides everything. Taking the last element is simple and is exactly why sorted input degrades to O(n²) — every partition peels off one item instead of splitting in half.
i = lo - 1i marks the end of the region known to be ≤ the pivot. Starting one before lo means that region is empty, which is true before anything has been examined.
if a[j] <= pivot: i += 1; swapGrow the small region by one slot and move the qualifying item into it. Everything between i and j is known to be larger than the pivot — that invariant is the whole partition.
a[i + 1], a[hi] = a[hi], a[i + 1]Puts the pivot in the gap between the two regions. It is now in its final sorted position and is never moved again, which is why the recursive calls skip index p.
quicksort(a, lo, p - 1); quicksort(a, p + 1, hi)Sorting happens in place with no merge step. That is quicksort's real advantage over merge sort — not speed on paper, but O(log n) extra space instead of O(n).
Change one thing
Swap in a middle pivot: a[(lo + hi) // 2], a[hi] = a[hi], a[(lo + hi) // 2] at the top of partition. The sorted-input depth collapses from n to log n.
Sort a list where every value is identical. Lomuto sends all of it to one side — the degenerate case that three-way partitioning exists to fix.
Raise the sorted sample to range(1, 2000) and run it. The recursion limit, not the running time, is what stops you.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Predict, then reveal
About to run: Watch a pivot settle permanently. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
With a last-element pivot, which input is quicksort's worst case?
Each partition peels off one element instead of halving, so the recursion goes n deep. The program prints depth 8 for a sorted 9-item list against 4 for a shuffled one.
After partition returns p, why do the recursive calls skip index p?
Everything left of p is smaller and everything right is larger, so p cannot move again. That is the one guaranteed piece of progress each partition makes.
Quicksort's advantage over merge sort is mainly:
Its worst case is worse and it is not stable. The memory profile, plus good cache behaviour, is what keeps it in use.
Cheat sheet
Quick Sort
Pick a pivot, partition around it, then recurse, and see why the pivot choice decides whether quick sort flies or crawls.
Engineering a Sort FunctionBentley & McIlroy, Software: Practice and Experience 1993
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.