← SciSim / Computer Science

⚡ Quicksort

Divide-and-Conquer | Partition-based Recursive Sort

Standard Undergraduate

§1 — Interactive Simulation

Array View
Complexity Graph
Pivot i-pointer (≤pivot zone) j-pointer (current) Sorted Out of range
Speed:
0
Comparisons
0
Swaps
0
Step
10
n
QUICKSORT(A, lo, hi):
  if lo < hi:
    p ← PARTITION(A, lo, hi)
    QUICKSORT(A, lo, p-1)
    QUICKSORT(A, p+1, hi)
PARTITION(A, lo, hi):
  pivot ← A[hi]
  i ← lo - 1
  for j ← lo to hi-1:
    if A[j] ≤ pivot: i++; swap(A[i],A[j])
  swap(A[i+1], A[hi])
  return i+1
Index Labels
Value Labels
Pointer Arrows
Swap Animation
Recurse Depth Bar

§2 — The Idea, Step by Step

Picture sorting a messy stack of graded exams by score. You grab one paper — call it the pivot — and make two piles: everyone who scored lower goes left, everyone higher goes right. That one paper is now sitting in its exact final rank, and you never touch it again. Then you play the same game on the left pile and the right pile, and on the piles inside those, until every pile is a single paper. The stack is sorted. That splitting move is the whole algorithm.

The single move that does all the work is the partition: walk through the group once, tossing each item to the correct side of the pivot. For a group of $n$ items that takes about $n-1$ comparisons — just one pass. If the pivot lands near the middle each time, the group roughly halves every round, so it takes about $\log_2 n$ rounds to shrink everything to singletons. One pass per round times $\log_2 n$ rounds gives roughly $n\log_2 n$ comparisons of work. For $n=16$ that is about $16\times4=64$ comparisons, versus $16^2=256$ for a clumsy compare-everything sort — already 4× cheaper, and the gap widens fast as $n$ grows.

The average-case recurrence writes this down precisely: $T(n)=2T(n/2)+(n-1)$, which the Master Theorem (Case 2) closes to $\Theta(n\log n)$. But quicksort's speed is hostage to the pivot. A balanced split gives that happy $\log_2 n$ depth; a terrible pivot — always the largest or smallest element — peels off just one item per round, so $T(n)=T(n-1)+(n-1)=\tfrac{n(n-1)}{2}=\Theta(n^2)$. That is the worst case the simulation reproduces when you feed it sorted data with a last-element pivot. The cure is to choose the pivot well: a random pivot or median-of-3 makes the bad case astronomically unlikely. In the panel above, the Pivot Strategy menu and the Preset selector map straight onto this — the pivot choice is the single variable that swings the entire runtime between $n\log n$ and $n^2$.

Try this in the sim above. (1) Set Preset to Worst Case with the last-element pivot and watch the recurse-depth bar march down one step at a time — that long chain is the $O(n^2)$ behavior. (2) Switch Pivot Strategy to Median-of-3 on the same sorted input and watch the depth collapse back toward $\log_2 n$. (3) Open the Complexity Graph tab and compare the $n\log n$ and $n^2$ curves — the widening gap between them is exactly what a good pivot choice buys you.

§3 — Complexity Analysis & Derivation

SymbolMeaning
nNumber of elements
T(n)Comparisons for array of size n
pPartition index (0-indexed)
T(k)Left subproblem of size k
T(n−k−1)Right subproblem
I(n)Inversions count
Step 1 — Partition Cost. PARTITION scans j from lo to hi−1: exactly n−1 comparisons for an array of size n. Pivot placed at final position.
Step 2 — Best Case Recurrence. Pivot always splits evenly: T(n) = 2T(n/2) + (n−1). By Master Theorem (a=2, b=2, f(n)=n): log₂2=1, f(n)=Θ(n¹) → Case 2 → T(n)=Θ(n log n).
Step 3 — Worst Case Recurrence. Pivot always smallest/largest: T(n) = T(0) + T(n−1) + (n−1) = T(n−1) + n−1. Telescoping: T(n) = Σᵢ₌₁ⁿ⁻¹ i = n(n−1)/2 = Θ(n²). Occurs on sorted/reverse-sorted input with last-element pivot.
Step 4 — Average Case (all permutations equally likely). \[T(n) = \frac{1}{n}\sum_{k=0}^{n-1}[T(k)+T(n-k-1)] + (n-1)\] By symmetry: T(n) = \(\frac{2}{n}\)Σ T(k) + n−1. Multiply both sides by n, subtract for n−1: nT(n) − (n−1)T(n−1) = 2T(n−1) + 2n−2. Divide by n(n+1): T(n)/(n+1) = T(n−1)/n + 2(n−1)/(n(n+1)). Summing: T(n) ≈ 2n ln n ≈ 1.386 n log₂n = Θ(n log n).
Step 5 — Space Complexity. In-place partition: O(1) extra data. But recursion depth: best/avg O(log n), worst O(n) call stack. Tail-call optimization on smaller partition reduces worst stack to O(log n).
Step 6 — Stability. NOT stable. Equal elements may be swapped relative order. Example: [3a, 3b, 1] with pivot=1 → swaps could reorder 3a,3b.
Step 7 — Why fastest in practice despite O(n log n) like Mergesort. Cache locality: accesses contiguous memory. No extra allocation. Low constant factors. Average case coefficient ≈1.39 vs mergesort ≈2. Branch prediction friendly on modern CPUs.

§4 — Frequently Asked Questions

Q1. Why is Quicksort O(n²) worst case but still preferred over Mergesort?concept▾
Quicksort's O(n²) worst case is practically avoidable via randomized pivot or median-of-3. In the average case it runs at ~1.39n log₂n comparisons vs Mergesort's ~n log₂n but Quicksort's cache behavior and zero extra allocation make it faster in wall-clock time by 2–3× on real hardware.
Q2. What does the simulation show when pivot is "Worst Case"?sim▾
With sorted input and last-element pivot, the pivot is always the maximum. PARTITION produces one partition of size n−1 and one empty partition. The recursion tree becomes a straight chain — you can see in the simulation how each call handles only one smaller subarray, stacking up O(n) comparisons per level.
Q3. How does Median-of-3 pivot selection help?applied▾
Median-of-3 picks the median of first, middle, and last elements as pivot. This eliminates the worst case for sorted/reverse-sorted inputs and in practice gives ~5–10% fewer comparisons than random pivot on average. It is the default strategy in many production sort implementations (e.g., Java's Arrays.sort for primitives before dual-pivot).
Q4. Why does Quicksort with random pivot have O(n log n) expected time?complex▾
With uniform random pivot, any element is equally likely to be the k-th smallest. The expected subproblem sizes are n/4 and 3n/4 with probability ≥ 1/2 (a "good" split). Good splits happen every 2 levels on average, giving a recursion tree of depth O(log n) with O(n) work per level. Formal analysis via the indicator random variable method gives E[T(n)] ≤ 2n ln n.
Q5. What is a 3-way partition (Dutch National Flag) and when to use it?nonobv▾
3-way partition splits the array into three regions: <pivot, =pivot, >pivot. This makes Quicksort O(n) when all elements are equal and O(nk) where k is the number of distinct keys. It is essential when there are many duplicates — the standard 2-way Lomuto/Hoare partition degrades badly on such inputs (try sorting [5,5,5,5,5] with the simulation!)
Q6. Introsort vs Quicksort — what does C++ std::sort actually use?deep▾
C++ std::sort uses Introsort: starts as randomized Quicksort, but switches to Heapsort when recursion depth exceeds 2⌊log₂n⌋, ensuring O(n log n) worst case. For small subarrays (n < 16) it switches to Insertion Sort due to lower overhead. This hybrid strategy gives the best of all three algorithms.

§5 — Common Misconceptions

Conceptual Misconceptions

❌ "Quicksort is always faster than Mergesort."

✅ Quicksort is faster on average with cache-friendly data, but Mergesort has guaranteed O(n log n) and is faster for linked lists or external sorting.

❌ "Pivot is always placed at the center after partition."

✅ Pivot ends up at its correct sorted position, which could be anywhere from index 0 to n−1 depending on input.

❌ "Quicksort is stable."

✅ Standard Quicksort is NOT stable. Equal elements can change relative order. Use Mergesort or TimSort if stability is required.

Implementation Misconceptions

❌ Using lo + (hi-lo)/2 as pivot is equivalent to picking the median.

✅ That picks the middle-index element, not the median value. Median-of-3 requires comparing values, not just averaging indices.

❌ Always using i < j in Lomuto partition (should be j < hi).

✅ In Lomuto scheme, j runs from lo to hi−1. The condition is j < hi (not j <= hi, which would include the pivot in comparisons).

❌ Forgetting base case: calling QUICKSORT(A, lo, lo) unnecessarily.

✅ The base case is lo < hi (strictly less). A single element (lo == hi) or empty range (lo > hi) must immediately return without partitioning.