Vibe Engines
ALGORITHMS · 03  /  QUICKSORT

The Pivot Pit.

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

  1. Pick a pivot. Here, the last element of the current range.
  2. Partition. Walk the range; keep a boundary i. Each element smaller than the pivot is swapped to the left of the boundary.
  3. Place the pivot. Swap it to the boundary — now everything left is smaller, right is larger, and the pivot is home for good.
  4. 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).

QUICK CHECK

Did it stick?

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).

RUN CARD

—

Next → a sort that guarantees O(n log n) and never melts down: merge sort.

Finished this one? 0 / 5 Algorithms done

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →