Comparison Sorts

Quick Sort

Pick a pivot, rearrange so everything smaller goes left and larger goes right. Recurse on both halves. Average O(n log n), worst O(n²) with bad pivots. In-place, not stable. The most commonly used sort in practice.

O(n log n) avg

O(log n)

How It Works

Quick sort picks a pivot element, then partitions the array in place so everything less than the pivot ends up to its left and everything greater to its right — placing the pivot in its final sorted position. It then recurses on the two sides independently. Lomuto's partition scans with one boundary pointer; Hoare's converges two pointers from both ends and does fewer swaps.

With balanced partitions the recursion depth is log n and each level does O(n) work, giving the O(n log n) average; a consistently bad pivot (already-sorted input with a first-element pivot) degrades to O(n^2), which randomized or median-of-three pivot selection makes vanishingly unlikely. Quick sort is in-place (O(log n) stack) but not stable, and its sequential memory access and tight inner loop give it the best constant factors among comparison sorts — hence its dominance in standard libraries for primitives.

Step-by-Step Visualization

QuickSort: pivot = 5 (last element)

Pivot5

1/3

Code

Java

static void quickSort(int[] arr, int lo, int hi) {
  if (lo >= hi) return;
  int pivot = arr[hi];
  int i = lo;
  for (int j = lo; j < hi; j++) {
    if (arr[j] < pivot) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i++; }
  }
  int tmp = arr[i]; arr[i] = arr[hi]; arr[hi] = tmp;
  quickSort(arr, lo, i - 1);
  quickSort(arr, i + 1, hi);
}

Tips & Gotchas

1Pick a pivot, partition array into smaller/larger halves

2Recursively sort each half

3Use random pivot to avoid worst case O(n²)

Practice Problems

1Sort an Array
2Sort Colors
3Kth Largest Element in an Array

About the Comparison Sorts Pattern

Sort by comparing pairs of elements. No comparison sort can do better than O(n log n) in the worst case — this is a proven lower bound. The three main ones differ in stability, space, and constant factors.

Key insight

Sorting unlocks binary search, two-pointer, and greedy. Always ask: can I sort first? Custom comparators solve tricky ordering problems. Know QuickSelect for O(n) expected Kth element.

Common Sorting Interview Problems

Sort Colors
Kth Largest Element
Merge Intervals
Largest Number
Sort List
Meeting Rooms

Frequently Asked Questions

How do I stop quick sort from hitting its O(n^2) worst case?

Randomize the pivot (or use median-of-three) so no fixed input pattern can consistently produce lopsided partitions; the expected time is then O(n log n) for every input. Production implementations like introsort additionally monitor recursion depth and switch to heap sort past 2*log n levels, capping the worst case at O(n log n).

Why do libraries use quick sort for primitives but merge sort for objects?

Quick sort is unstable, which is invisible for primitive values since equal primitives are indistinguishable, and its cache behavior and in-place operation make it fastest. Sorting objects, equal keys can carry different payloads whose relative order users rely on, so stable algorithms like Timsort are used despite the O(n) auxiliary space.

How does three-way partitioning help with many duplicate keys?

Standard partitioning keeps recursing into runs of equal elements, wasting work. Dutch national flag partitioning splits into less-than, equal, and greater-than regions, so all duplicates of the pivot are finished immediately — arrays with few distinct keys sort in close to O(n) time.