A high-efficiency "Divide and Conquer" algorithm that partitions data around a pivot to sort recursively.
Overview
Partitioning, not merging
Quick sort is divide-and-conquer with the work moved to the front. Choose a pivot element. Rearrange the array so that everything less than the pivot sits to its left and everything greater sits to its right — the pivot is now in its final sorted position, permanently. Recurse on the left part and the right part.
There is no combine step. Once both sides are sorted, the array is sorted, because partitioning already placed everything on the correct side. That is the mirror image of merge sort, which splits trivially and does all its work merging.
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)
Quick Sort: A Practical Guide
Pick a pivot, push everything smaller to its left and everything larger to its right, then recurse on both sides. Fastest sort in practice, and the only common one whose worst case is quadratic.
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], and everything is placed. Note the second partition was badly unbalanced — 0 elements against 3 — which is exactly the behaviour that causes the worst case.
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 this is triggered by already-sorted input — the most common real-world case, which is why naive quick sort is dangerous.
The saving grace is that the average is robustly O(n log n). Even a split as lopsided as 90/10 at every level still gives logarithmic depth, just with a larger base. You need consistently near-worst pivots to reach quadratic, and randomising the pivot makes that vanishingly unlikely for any fixed input.
Partition, then recurse
Quick sort picks an element as the pivot, rearranges the array so everything smaller sits left of it and everything larger sits right, and then sorts each side recursively.
After one partition the pivot is in its final position, and the two sides are independent problems.
Sorting [38, 27, 43, 3, 9, 82, 10] with 10 as the pivot:
Step
Result
Partition on 10
[3, 9] 10 [38, 27, 43, 82]
Sort left
[3, 9]
Sort right on pivot 43
[27, 38] 43 [82]
Combined
[3, 9, 10, 27, 38, 43, 82]
No merge step is needed, which is the structural difference from merge sort: quick sort does its work before recursing, merge sort after.
Why the pivot decides everything
A good pivot splits the array roughly in half, giving log n levels of recursion with O(n) work each — O(n log n).
A bad pivot splits off one element, giving n levels — O(n²).
Pivot quality
Recursion depth
Complexity
Median every time
log n
O(n log n)
Random
~1.4 log n expected
O(n log n) expected
Always the smallest
n
O(n²)
The classic trap: choosing the first element as the pivot makes already-sorted input the worst case. Sorted input is extremely common in practice, so this is not a theoretical concern — it is the most likely input in many systems.
Two standard fixes:
Randomised pivot. Choose uniformly at random. The worst case still exists and requires adversarial luck; expected time is O(n log n).
Median-of-three. Take the median of the first, middle and last elements. Cheap, deterministic, and it handles sorted and reverse-sorted input well.
Production implementations go further: introsort starts with quick sort, tracks recursion depth, and switches to heap sort if it exceeds 2 log n — guaranteeing O(n log n) while keeping quick sort's speed in the common case. That is what C++'s std::sort does.
Lomuto partitioning
The simpler of the two classic schemes, and the one worth memorising:
def quicksort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo >= hi:
return
p = partition(arr, lo, hi)
quicksort(arr, lo, p - 1)
quicksort(arr, p + 1, hi)
def partition(arr, lo, hi):
import random
random.seed() # randomised pivot
r = random.randint(lo, hi)
arr[r], arr[hi] = arr[hi], arr[r] # move pivot to the end
pivot = arr[hi]
i = lo # boundary of the "smaller" region
for j in range(lo, hi):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[hi] = arr[hi], arr[i] # pivot into place
return i
The invariant is what makes it work: everything left of i is smaller than the pivot, everything from i to j is larger, and j scans forward. When the loop ends, swapping the pivot into position i puts it exactly where it belongs.
Note the in-place property: no auxiliary array, only swaps. That is quick sort's main advantage over merge sort.
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. Occasionally one side gets almost everything; that single unbalanced level is a small dose of the worst case.
Compare the recursion shape with merge sort. Merge sort’s tree is always perfectly balanced because it splits by position. Quick sort’s depends entirely on the values, so the tree is lopsided and different on every run.
Scale it. Run a full sort at Array Size 5 and then 25. The comparison count grows roughly like n log n, noticeably slower than the n² growth of insertion sort at the same sizes.
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, needing only O(log n) stack space for the recursion. Merge sort needs an O(n) buffer, and allocating and touching it costs real time.
Cache behaviour. Partitioning sweeps two pointers inward through contiguous memory, which 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 defend the worst case rather than accepting it: median-of-three or random pivot selection makes sorted input harmless, and introsort — the C++ standard library’s sort — counts recursion depth and switches to heap sort if it exceeds 2 log n, converting the quadratic worst case into a guaranteed O(n log n).
Common mistakes
Always taking the first or last element as pivot. This makes already-sorted input the worst case, which 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.
The short version
Quick sort partitions around a pivot, placing that pivot permanently and recursing on both sides with no combine step. In-place, cache-friendly and with a small constant factor, it is the fastest general-purpose array sort in practice — provided the pivot is chosen so that sorted input is not the worst case. Its O(n²) ceiling is real but avoidable, and every serious implementation avoids it by randomising the pivot or by falling back to heap sort when the recursion runs too deep.
Quick sort against merge sort
Quick sort
Merge sort
Average time
O(n log n)
O(n log n)
Worst time
O(n²)
O(n log n)
Extra space
O(log n) stack
O(n)
Stable
No
Yes
Cache behaviour
Excellent
Good
Typical speed
Faster
Slower constant factor
Quick sort wins in practice on arrays despite the worse guarantee, for two reasons. It sorts in place, so no large auxiliary allocation. And its memory access pattern is sequential within each partition, which suits CPU caches well.
Merge sort wins where its guarantees matter: stability (equal elements keep their relative order, which matters when sorting by one key after another), a hard O(n log n) bound, and external sorting of data too large for memory.
Python's sorted uses Timsort, a merge sort variant that detects existing sorted runs and merges them, giving O(n) on nearly-sorted input — and it is stable, which Python guarantees.
Duplicates, and three-way partitioning
Plain Lomuto partitioning handles many equal elements badly. If every element is identical, each partition splits off one element and the algorithm degrades to O(n²).
Three-way partitioning (the Dutch national flag arrangement) splits into three regions — less than, equal to, and greater than the pivot — and recurses only on the outer two. All the equal elements are placed in one pass.
That turns an array of many duplicates from the worst case into the best case: sorting n identical elements becomes O(n).
It is worth knowing because arrays with few distinct values are common in real data — status flags, categories, boolean columns — and this is the variant that handles them.
Quickselect: the same idea for the k-th element
Partitioning tells you the pivot's final position. If that position is k, the pivot is the k-th smallest element and no further work is needed. If not, recurse into only the side containing k.
Quickselect is that algorithm, and it finds the k-th smallest element in O(n) expected time rather than the O(n log n) of sorting.
Uses: finding a median, the top k items, or a percentile without sorting the whole array. Python's heapq.nlargest uses a heap instead, which is better when k is small; quickselect wins for a median.
The pivot is the algorithm
Quick sort's average case and its worst case are the same code with a different pivot rule. That makes it a good thing to measure rather than describe: the same input, four pivot strategies, and the comparison counts tell you which choices are safe and which are a denial-of-service waiting to happen.
example_01.pyPython
import random
def quick(a, pick, stats, depth=0):
stats["depth"] = max(stats["depth"], depth)
if len(a) <= 1:
return a
p = pick(a)
lo, eq, hi = [], [], []
for x in a:
stats["comps"] += 1
(lo if x < p else hi if x > p else eq).append(x)
return (quick(lo, pick, stats, depth + 1) + eq +
quick(hi, pick, stats, depth + 1))
first = lambda a: a[0]
last = lambda a: a[-1]
rand = lambda a: a[random.randrange(len(a))]
def median3(a):
lo, mid, hi = a[0], a[len(a) // 2], a[-1]
return sorted([lo, mid, hi])[1]
n = 100
inputs = {
"random": random.Random(5).sample(range(n), n),
"sorted": list(range(n)),
"reversed": list(range(n))[::-1],
"all equal": [7] * n,
}
picks = [("first", first), ("last", last), ("random", rand),
("median-of-3", median3)]
print("n = %d, comparisons (max recursion depth)" % n)
print("%-12s %16s %16s %16s %16s" % tuple(
["pivot"] + list(inputs.keys())))
for pname, pick in picks:
row = []
for data in inputs.values():
random.seed(1)
st = {"comps": 0, "depth": 0}
quick(data, pick, st)
row.append("%d (%d)" % (st["comps"], st["depth"]))
print("%-12s %16s %16s %16s %16s" % tuple([pname] + row))
import math
print()
print("for reference: n^2/2 = %d, n log2 n = %.0f" % (n * n // 2, n * math.log2(n)))
# Read the "sorted" and "reversed" columns for the first and last pivots.
# Those are the quadratic cases, and note the recursion depth: 99 frames
# deep on 100 elements. In a language without deep stacks this is not a
# slow sort, it is a crash.
#
# Now read "all equal". Every element goes into eq, so the three-way
# partition finishes in ONE level for every pivot rule. A two-way
# partition -- the more common Lomuto version, which sends equal elements
# to one side -- goes quadratic here instead. Repeated values are a real
# input, and the three-way split is why this version survives them.
#
# The random and median-of-3 rows stay within a small factor of
# n log2 n = 664 on every input. That
# is the practical fix: not a better average, but no input that an
# attacker can choose to make it quadratic. Median-of-3 is deterministic,
# so a determined attacker can still construct a killer sequence; random
# pivots cannot be targeted in advance.
Output
Questions people ask
Why use quick sort if the worst case is O(n²)? With randomised or median-of-three pivots the worst case is practically unreachable, and its in-place operation and cache behaviour make it faster than merge sort in the average case.
Is quick sort stable? No — partitioning swaps distant elements. Use merge sort or Timsort if stability matters.
How much extra memory does it use? O(log n) for the recursion stack, and O(n) in the degenerate case. Tail-call elimination on the larger side bounds it.
What does Python use? Timsort, which is a stable merge sort exploiting existing runs. list.sort() and sorted() both use it.
When is merge sort better? Linked lists (no random access needed), external sorting, and whenever stability or a hard worst-case bound is required.
What is introsort? Quick sort that switches to heap sort when recursion gets too deep, giving a guaranteed O(n log n) with quick sort's typical speed.
Recap in one screen
Partition around a pivot so the pivot lands in its final position, then recurse on each side.
The pivot choice decides everything: randomised or median-of-three, never the first element.
In-place with good cache behaviour, which is why it beats merge sort in practice despite the O(n²) worst case.
Not stable; use Timsort or merge sort when equal elements must keep their order.
Three-way partitioning handles many duplicates, and quickselect finds the k-th element in O(n).
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.
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
Quick sort is divide-and-conquer with the work moved to the front. Choose a pivot element. Rearrange the array so that everything less than the pivot sits to its left and everything greater sits to its right — the pivot is now in its final sorted position, permanently. Recurse on the left part and the right part.
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.