Quick Sort Complete Guide

Video Explainer

Prefer video learning? This explainer gives a quick visual walkthrough of the core idea before you dive into the detailed sections below.

Related Sorting Guides

Bubble, merge, and quick sort are tightly related. Compare them side-by-side to understand tradeoffs in runtime, memory, and stability.

Core Concepts

Learn the core building blocks and terminology in one place before comparisons, so the mechanics are clear and duplicates are removed.

How It Compares

Real-World Stories and Company Examples

Lomuto-partition quick sort

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
}

Common Problems and Failure Modes

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

Tips and Tricks

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

When to Use

Use these signals to decide if this data structure/algorithm is the right fit before implementation.

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 (including 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.