Quick Sort Complete Guide

Algorithm • hard

Quick sort partitions around a pivot so smaller values move left and larger values move right.

It is often one of the fastest general-purpose sorts in practice due to cache-friendly partitioning.

Its worst case is O(n^2), so pivot strategy and randomization matter.

Typical Complexity Baseline

Metric	Value
Average	`O(n log n)`
Worst	`O(n^2)`
Space	`O(log n)` recursion

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

Quick sort partition around a pivot

After partitioning, every left-side value is ≤ pivot and every right-side value is > pivot.

Step 1/10Pick pivot = arr[last] = 4. i = boundary (left of which everything ≤ pivot). j = scan.

Speed

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

Quick sort in 4 minutes

Channel: Michael Sambol

Watch on YouTube →

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Pivot selection

What it is Chosen value used to split array into two regions.

Why it matters Pivot selection is a required building block for understanding how Quick Sort stays correct and performant on large inputs.

Partition procedure

What it is Reorder elements around pivot boundary.

Why it matters Partition procedure is a required building block for understanding how Quick Sort stays correct and performant on large inputs.

Recursive subproblems

What it is Sort left and right partitions recursively.

Why it matters Recursive subproblems is a required building block for understanding how Quick Sort stays correct and performant on large inputs.

Recursion depth control

What it is Tail recursion/randomized pivot to limit worst-case behavior.

Why it matters Recursion depth control is a required building block for understanding how Quick Sort stays correct and performant on large inputs.

In-place swaps

What it is Partition done directly on original array.

Why it matters In-place swaps is a required building block for understanding how Quick Sort stays correct and performant on large inputs.

Pivot

What it is Reference element used for partitioning step.

Why it matters Reference element used for partitioning step. In Quick Sort, this definition helps you reason about correctness and complexity when inputs scale.

Partition index

What it is Final pivot location after partitioning.

Why it matters Final pivot location after partitioning. In Quick Sort, this definition helps you reason about correctness and complexity when inputs scale.

Randomized quicksort

What it is Random pivot choice to reduce adversarial patterns.

Why it matters Random pivot choice to reduce adversarial patterns. In Quick Sort, this definition helps you reason about correctness and complexity when inputs scale.

Tail recursion

What it is Optimization style to reduce stack growth.

Why it matters Optimization style to reduce stack growth. In Quick Sort, this definition helps you reason about correctness and complexity when inputs scale.

Quickselect

What it is Partition-based algorithm to find kth statistic without full sort.

Why it matters Partition-based algorithm to find kth statistic without full sort. In Quick Sort, this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/10

Pick pivot = arr[last] = 4. i = boundary (left of which everything ≤ pivot). j = scan.

Step 2/10

j=0 · arr[0]=7 > 4 → skip. i stays.

Step 3/10

j=1 · arr[1]=7 ≤ 4 → swap with i=0. i++.

Step 4/10

j=2 · arr[2]=9 > 4 → skip. i stays.

Step 5/10

j=3 · arr[3]=7 ≤ 4 → swap with i=1. i++.

Step 6/10

j=4 · arr[4]=5 > 4 → skip. i stays.

Step 7/10

j=5 · arr[5]=8 > 4 → skip. i stays.

Step 8/10

j=6 · arr[6]=9 ≤ 4 → swap with i=2. i++.

Step 9/10

j=7 · arr[7]=6 > 4 → skip. i stays.

Step 10/10

Final swap: arr[3] ↔ pivot. Pivot 4 sits at index 3. Left of it: ≤4. Right: >4. Recurse on each side (not shown).

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. Merge Sort

Choose this when Choose quick sort for in-place average-case speed.

Tradeoff Merge sort has better worst-case guarantee and stability.

vs. Heap Sort

Choose this when Choose quick sort for practical cache-local performance.

Tradeoff Heap sort avoids O(n^2) worst case but can be slower in practice.

vs. Bubble Sort

Choose this when Choose quick sort for any real production sorting workload.

Tradeoff Bubble is only useful for pedagogy or tiny lists.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

Language runtimes

Many standard library sort implementations use quicksort-inspired partitioning hybrids (often introsort variants).

Takeaway Quick sort ideas are still central in production-grade sort engines.

Search ranking systems

Ranking pipelines repeatedly order candidate sets where partition-style selection helps prune work.

Takeaway Partitioning concepts help both full sorting and top-k retrieval.

Ad-tech bidding systems

Latency-sensitive auction logic benefits from fast in-memory ordering of medium-size candidate arrays.

Takeaway Average-case speed and memory locality are decisive in low-latency loops.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

Partition around pivot, then recursively sort left and right partitions.

Complexity: Average O(n log n), Worst O(n^2), Space O(log n) recursion average

Lomuto-partition quick sort

Language

function quickSort(values: number[], leftIndex = 0, rightIndex = values.length - 1): number[] {
  if (leftIndex >= rightIndex) return values

  const pivotValue = values[rightIndex]
  let storeIndex = leftIndex
  for (let scanIndex = leftIndex; scanIndex < rightIndex; scanIndex += 1) {
    if (values[scanIndex] <= pivotValue) {
      ;[values[storeIndex], values[scanIndex]] = [values[scanIndex], values[storeIndex]]
      storeIndex += 1
    }
  }

  ;[values[storeIndex], values[rightIndex]] = [values[rightIndex], values[storeIndex]]
  quickSort(values, leftIndex, storeIndex - 1)
  quickSort(values, storeIndex + 1, rightIndex)
  return values
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

Choosing first/last pivot on nearly sorted input causing O(n^2).
Incorrect partition boundaries leading to infinite recursion.
Ignoring recursion-depth limits on huge arrays.
Assuming quick sort is stable when it is usually not.
Not switching to insertion sort for tiny partitions in optimized implementations.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

Pivot strategy drives performance; randomized or median-style pivots reduce worst-case risk.
Partition correctness is everything; test with duplicates and nearly sorted input.
Quick sort is often fastest in practice but not stable by default.
Switch to insertion sort for tiny partitions in optimized implementations.

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

Real-system usage signals

Strong average-case performance with low constant factors.
In-place partitioning requires less extra memory than merge sort.
Related partition logic underpins quickselect for kth-element problems.

LeetCode-specific tips (pattern-identification signals)

Identification signal: partition-around-pivot approach with strong average performance is acceptable.
Identification signal: in-place sorting with cache-friendly behavior is preferred and worst-case can be mitigated.
If prompt discusses pivot strategy or partitioning, quick-sort family is likely intended.
For Quick Sort questions, start by naming the core invariant before writing code.
Use the constraint section to set time/space target first, then pick the data structure/algorithm.
Solve one tiny example by hand and map each transition to your variables before implementing.
Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#	Problem	Difficulty	Typical Complexity
1	Sort an Array	Medium	`O(n log n)` average
2	Kth Largest Element in an Array	Medium	`O(n)` avg quickselect
3	Top K Frequent Elements	Medium	`O(n log k)`
4	Wiggle Sort II	Medium	`O(n log n)`
5	Largest Number	Medium	`O(n log n)`
6	Sort Colors	Medium	`O(n)`
7	K Closest Points to Origin	Medium	`O(n log k)`
8	Median of Two Sorted Arrays	Hard	`O(log(min(m,n)))`
9	Count of Smaller Numbers After Self	Hard	`O(n log n)`
10	Reverse Pairs	Hard	`O(n log n)`