Quicksort is a divide-and-conquer sorting algorithm. It picks a 'pivot' element, partitions the array so everything smaller is on its left and everything larger on its right (which puts the pivot in its final sorted position), then recursively sorts the two sides. It sorts in place and is one of the fastest comparison sorts in practice.

No, standard quicksort is not stable — equal elements can be reordered during partitioning. If you need a stable sort, use merge sort. Quicksort is usually chosen for its in-place memory use and excellent cache performance rather than stability.

Quicksort vs merge sort — which is better?

Quicksort sorts in place (O(log n) extra memory) and is typically faster in practice thanks to cache locality, but it has an O(n²) worst case and is not stable. Merge sort guarantees O(n log n) and is stable, but needs O(n) extra memory. Quicksort wins for in-memory arrays; merge sort is preferred for linked lists, external sorting, and when stability or a guaranteed bound matters.

Why do real-world libraries randomize the pivot or use median-of-three?

A fixed pivot (like 'always the last element') has predictable worst-case inputs that an attacker or just sorted data can trigger, causing O(n²) blowups. Choosing the pivot randomly, or as the median of the first, middle and last elements, makes any specific input unlikely to be the worst case, keeping the expected running time at O(n log n).

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

ALGORITHMS · 03 / QUICKSORT

The Pivot Pit.

Watch the explainer

Pick a pivot, shove everything smaller left and everything bigger right, repeat. Watch it sort in place — then feed it a sorted list and watch it melt to O(n²).

THE GIST · 20 SECONDS

Quicksort picks a pivot, partitions the array so smaller values sit left and larger right — which drops the pivot into its final sorted spot — then recurses on each side. It sorts in place in O(n log n) on average, but a bad pivot can make it O(n²). It's the default sort under the hood of many languages.

Pivotthe element everything is compared to
Partitionsmaller-left, larger-right rearrange
In placesorts with O(1) extra array space
Worst caseO(n²) when the pivot is always extreme

① Watch the pivot partition → ② Pick your own pivot → ③ Break the worst case

pivot boundary (i) scanning (j) in final place

The boundary (i) is a promise: everything to its left is already smaller than the pivot. j scans ahead; each bar smaller than the pivot gets swapped behind the boundary.

UNDER THE HOOD

What you just watched, written down

You saw the pivot partition the array and the worst case melt it down. Here's the same thing as code.

How the pivot thinks — the loop

Pick a pivot. Here, the last element of the current range.
Partition. Walk the range; keep a boundary i. Each element smaller than the pivot is swapped to the left of the boundary.
Place the pivot. Swap it to the boundary — now everything left is smaller, right is larger, and the pivot is home for good.
Recurse on the left part and the right part, until ranges shrink to one element.

AVERAGE vs WORST

Balanced splits give log n levels × O(n) work = O(n log n). Always-extreme pivots give n levels = O(n²). Randomizing the pivot keeps you in the good case.

The algorithm (Lomuto partition)

function quicksort(a, lo, hi):
    if lo >= hi: return
    p = partition(a, lo, hi)
    quicksort(a, lo, p - 1)
    quicksort(a, p + 1, hi)

function partition(a, lo, hi):
    pivot = a[hi]                # last element
    i = lo
    for j in lo .. hi - 1:
        if a[j] < pivot:
            swap(a[i], a[j]); i++
    swap(a[i], a[hi])           # pivot to its home
    return i

TIME (avg)O(n log n)O(n²) worst · O(n log n) best

SPACEO(log n)in place · recursion stack

Solved by hand — the partitions for the array above

Each partition, the pivot it used, and the index where that pivot landed for good.

⚠ The worst case is real

A fixed last-element pivot on sorted or reverse-sorted input is O(n²) — a denial-of-service waiting to happen. Always randomize the pivot or use median-of-three.

↔ Quicksort vs merge sort

Quicksort: in place, cache-friendly, fast — but O(n²) worst and not stable. Merge sort: guaranteed O(n log n) and stable, but needs O(n) extra memory.

★ Where it's used

The default in-memory sort behind many standard libraries (often as introsort: quicksort that falls back to heapsort to dodge the worst case).

The picture: one partition pass

A single pass of the Lomuto partition with the last element as pivot, on [7, 2, 9, 4, 3, 8, 1, 5]. Seven comparisons later the four values below 5 are packed on the left, the three above it on the right, and 5 sits at index 4, where it will stay. Neither side is sorted yet, but the sides never need to talk to each other again.

Complexity and trade-offs

Case	Time	Space	Why
Last-element pivot, random input	`O(n log n)` average	`O(log n)` expected stack	n = 1,000 shuffled (`Random(1)`): 11,638 comparisons and recursion depth 23. For scale, n log₂ n is about 9,966.
Last-element pivot, sorted input	`O(n²)`	`O(n)` stack	Same n, already sorted: 499,500 comparisons (exactly n(n−1)/2) and depth 1,000. Reverse-sorted input gives the same numbers.
Random pivot, sorted input	`O(n log n)` expected	`O(log n)` expected	Same sorted input, pivot from `Random(2)`: 12,521 comparisons, depth 24.
Median-of-three pivot	`O(n log n)` typical	`O(log n)` typical	Sorted input: 7,987 comparisons, depth 10. Random input: 9,526, depth 17. Specially built inputs can still defeat it.
Merge sort	`O(n log n)` always	`O(n)` extra	Random input: 8,705 comparisons; sorted: 4,932. Stable, but needs a buffer.

Comparison counts are not the whole story: quicksort does more of them than merge sort here (11,638 against 8,705), so any practical edge comes from sorting in place and scanning memory sequentially, not from doing less comparing. The cliff is the sorted row. A fixed pivot turns the most common real-world input, data that is already in order, into a quadratic run with a call stack as deep as the array. Python’s built-in sort, which looks for runs, needed only 999 comparisons on the sorted array. Any of the three pivot fixes puts quicksort back within a small factor of n log n.

Common mistakes

Many equal keys with a strict comparison
On 1,000 copies of the same value, a Lomuto pass that moves only elements smaller than the pivot moves nothing, leaves the pivot at the end, and recurses on n−1 elements: 499,500 comparisons. A three-way partition (smaller, equal, larger) finishes the same input in one pass of 1,000 loop iterations, because the whole equal block is final.
Recursing on <code>(lo, p)</code> instead of <code>(lo, p - 1)</code>
That is the Hoare-style bound grafted onto Lomuto, where the pivot is already home. Run on [1, 2], the pivot 2 lands at index 1 and the call (0, 1) repeats forever; it raises a recursion error. [3, 1, 2] fails the same way.
Trusting the call stack with a fixed pivot
With the last element as pivot and a sorted array of 1,000 items, the depth is 1,000 frames. Python’s default recursion limit is 1,000, so the sort raises RecursionError at n = 1,000 and 2,000, while n = 500 passes. Other languages overflow at a different depth, but the failure is the same.
Recursing on the larger half
The stack is bounded by O(log n) only if you recurse on the smaller part and loop on the larger. With that rule, the maximum depth was 2 on sorted input, 2 on reversed input and 7 on the random shuffle, against 1,000 for the plain two-call version on sorted data.
Assuming it is stable
Sort the records (1,a) (1,b) (2,c) (2,d) by key with Lomuto and the output is (1,b) (1,a) (2,d) (2,c): both pairs of equal keys come out reversed. If order among equal keys matters, use a stable sort or add the original index to the key.

Where this shows up

Selecting without sorting (quickselect)
To find the median or the k-th smallest, partition and then recurse into only the side that holds position k. On the 1,000-item shuffle above, finding the middle element (a random pivot, Random(5)) took 3,049 comparisons, about 3n, where sorting took 11,638.
Hybrid library sorts
Introsort starts as quicksort, switches to heapsort when the recursion gets too deep, and often finishes small ranges with insertion sort. It keeps the average speed and removes the quadratic cliff.
Partition as a building block
The three-way partition used above to handle duplicates is the Dutch national flag routine; the same pass sorts an array that holds only three distinct values in linear time.
In-memory sorting of arrays
It works in place and scans the array sequentially, which suits fast caches. It is a poor fit for data that must be sorted stably, or that does not fit in memory, where merge-based external sorts are used.

RUN IT YOURSELF

Quicksort, in Python & TypeScript

The same divide-and-conquer sort in both languages, running for real in your browser — Python via WebAssembly, TypeScript transpiled on the fly. Switch tabs to compare them, read the numbered comments, edit anything, and hit Run (or ⌘/Ctrl + Enter).

HOW TO READ THE CODE — 4 IDEAS

A slice of 0 or 1 items is already sorted — the base case (step 1).
Pick a pivot and compare every other item to it (step 2).
Everything smaller goes left, larger goes right (step 3).
Recursively sort both sides, then glue left + pivot + right (step 4).

CPython · WebAssembly

QUICK CHECK

Did it stick?

See every answer, with the reasoning

What is the average time complexity of quicksort?
Answer: O(n log n) — Balanced partitions give log n levels of O(n) work each — O(n log n) on average and in the best case.
When does quicksort hit its O(n²) worst case?
Answer: When the pivot is consistently the smallest or largest element — Always-extreme pivots peel off one element per partition (n levels). A last-element pivot on sorted data triggers exactly this.
After a partition, the pivot is…
Answer: in its final sorted position — Partitioning puts all smaller elements left and larger right, so the pivot is exactly where it belongs in the sorted array — permanently.

FAQ

Quicksort, answered

What is quicksort?

Quicksort is a divide-and-conquer sort: pick a pivot, partition so smaller values go left and larger right (placing the pivot in its final spot), then recurse on each side. It sorts in place and is one of the fastest comparison sorts in practice.

What is the time complexity of quicksort?

O(n log n) average and best, O(n²) worst (consistently extreme pivots). Randomizing the pivot makes the worst case astronomically unlikely. Space is O(log n) for the recursion stack.

Why is quicksort O(n²) in the worst case?

If every pivot is the smallest or largest element, each partition peels off just one element instead of halving — giving n levels of O(n) work. A last-element pivot on sorted data triggers exactly this.

Is quicksort stable?

No — equal elements can be reordered during partitioning. Use merge sort if you need a stable sort.

Quicksort vs merge sort?

Quicksort is in-place and cache-friendly but O(n²) worst and unstable. Merge sort is guaranteed O(n log n) and stable but needs O(n) extra memory. Quicksort for in-memory arrays; merge sort for linked lists, external sorting, or when stability matters.

Why randomize the pivot or use median-of-three?

A fixed pivot has predictable worst-case inputs (sorted data, or a malicious input) that blow up to O(n²). A random or median-of-three pivot makes any specific input unlikely to be the worst case, keeping the expected time at O(n log n).

▶ Watch it explained

Quicksort: Time and Space Complexity, From First Principles

Finished this one? 0 / 99 Algorithms done

NextThe Tournament: Heap Sort Next on the “The comparison sorts” ladder · rung 3 of 4

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

More Algorithms

Explore more

Algorithms →