19

Sorting

Put things in order once, and a dozen hard problems turn easy.

intermediate~75 min7 simulations7 problems

▶ guided lesson⚡ 1-minute summary↻ 14 recall cards

before this: Arrays & Strings · Big-O · Recursion · Two Pointers

01 · why it exists

Why this exists, and the weight it carries

since1956–1962

Insertion sort (and the other O(n²) sorts)

E. H. Friend (1956 survey) · Kenneth E. Iverson (the name "bubble sort", 1962)

The simple sorts are older than their names. In 1956 E. H. Friend's survey in the Journal of the ACM compared methods such as inserting and exchanging — and found exchanging needs at least twice as many comparisons as inserting. Owen Astrachan's 2003 history of bubble sort found early books calling it "exchange sorting"; the first use of the name bubble sort in print he could find is Iverson's 1962 book A Programming Language. Knuth's verdict: bubble sort "seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems".

the problem it solvedSorting small amounts of data on early machines with almost no spare memory — and, today, finishing tiny or nearly sorted ranges faster than any O(n log n) sort can.

its jobs today

  • Inside Java's own sorts: TimSort sorts arrays under 32 elements with binary insertion sort, and the dual-pivot quicksort switches to insertion-sort variants for small ranges (JDK 17 source).
  • Keeping a short list sorted while items arrive one at a time — a top-10 leaderboard, a recent-files menu: each new item slides into place.

the weight it carries

Illustrative: 10,000 contacts already sorted by name, plus 10 new ones added at the end (n = 10,010). Insertion sort's work is n − 1 comparisons plus one shift per out-of-order pair: at most 10,009 + 10 × 10,009 ≈ 1.1 lakh steps. The same contacts in random order: about n²/4 ≈ 2.5 crore shifts.

without it

Library sorts would waste recursion and bookkeeping on 5-element ranges, and nearly sorted data would cost as much as random data.

when · why · how

when
n is tiny (a few dozen), the data is nearly sorted, or items arrive one by one into a list that is already sorted.
why
Work = n + number of inversions: O(n) on sorted input, O(n²) on reversed input; O(1) extra space and stable. Bubble sort never beats it; selection sort only wins when writes are very expensive (at most n − 1 swaps).
how
for (int i = 1; i < n; i++) { int key = a[i], j = i - 1; while (j >= 0 && a[j] > key) a[j + 1] = a[j--]; a[j + 1] = key; } — the strict > keeps it stable.

02 · plain english

The idea in 30 seconds

Sorting puts equal and nearby values next to each other — duplicates, overlaps and gaps become neighbours you can see in one pass.

Simple sorts compare neighbours and cost O(n²). Divide and conquer (merge, quick, heap) gets to O(n log n) — the best any comparison sort can do.

If values are small integers you can skip comparisons entirely and count them in O(n + k).

picture this

Clicking a column header in File Explorer or Excel: no row changes, only the order does — and suddenly the biggest file is on top, duplicate names sit together, and a missing invoice number jumps out. Sorting is that click, done in code.

03 · remember

What you must know

  • Comparison sorts can't beat O(n log n) in the worst case: n! possible orders need at least log₂(n!) ≈ n log n yes/no questions to tell apart.
  • Stable = equal keys keep their original order. It matters when you sort records by one field after another (sort by name, then stably by age).
  • In-place = O(1) (or O(log n)) extra memory. Merge sort is not in-place on arrays; quick and heap sort are.
  • Adaptive = faster on nearly-sorted input. Insertion sort (and TimSort, built on it) runs in O(n) on sorted data.
  • Quicksort is fastest in practice but O(n²) with bad pivots — random pivots make that vanishingly unlikely; median-of-three helps on ordinary data, but crafted inputs can still force it.
  • Merge sort is O(n log n) always, stable, and is the sort for linked lists and for counting things like inversions.
  • Java: Arrays.sort(int[]) = dual-pivot quicksort (not stable, no one can tell equal ints apart). Arrays.sort(Object[]) / Collections.sort = TimSort, stable.
  • Never write (a, b) -> a - b — it overflows. Use Integer.compare(a, b) or Comparator.comparingInt(...).

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

Bubble sort — the biggest value bubbles right

Neighbours swap until each pass parks the largest remaining value at the end (lime). A pass with no swaps ends the sort early.

loading simulation…
sim

Selection sort — pick the minimum, swap it to the front

Always n(n−1)/2 comparisons, but at most n−1 swaps. Watch a long-distance swap break stability.

loading simulation…
sim

Insertion sort — slide each new value into place

The left part is always sorted. Each new key slides left past bigger values. Try a nearly-sorted input: almost no work.

loading simulation…
sim

Merge sort — split, sort halves, zip them together

The lower layer is the helper array. Two pointers (i, j) walk the sorted halves; the smaller head is written back at k.

loading simulation…
sim

Merge sort on a linked list — relink, don't copy

Runs of width 1, 2, 4… are cut off and merged by changing next pointers only. No helper array, no recursion: O(1) extra space.

loading simulation…
sim

Quicksort — Lomuto partition

Values smaller than the pivot (amber) gather on the left. The pivot then drops between the zones and is final forever.

loading simulation…
sim

Counting sort — no comparisons at all

Tally into buckets, turn counts into end positions (prefix sums), then place right-to-left. The #ids show equal values keep their order.

loading simulation…

05 · cost

Time & space, explained

Every sort at a glance
BestAverageWorstExtra spaceStableIn-placewhy
Bubble sort (early exit)O(n)O(n²)O(n²)O(1)YesYesBest: one pass with no swaps on sorted input. Otherwise each pass fixes one value: (n−1)+(n−2)+… = n(n−1)/2 comparisons.
Selection sortO(n²)O(n²)O(n²)O(1)NoYesIt always scans the whole unsorted part to find the minimum — even if the array is sorted. Its long swaps can jump an element over its equal twin.
Insertion sortO(n)O(n²)O(n²)O(1)YesYesWork = number of inversions. Sorted input has none (n−1 comparisons); reversed input has n(n−1)/2.
Merge sort (top-down)O(n log n)O(n log n)O(n log n)O(n)YesNolog₂ n levels of halving; each level merges n values. The helper array costs n extra slots (plus O(log n) recursion).
Quicksort (random pivot)O(n log n)O(n log n)O(n²)O(log n) expectedNoYesBalanced pivots halve the range → log n levels of O(n) partitioning. Always picking the min/max gives n levels → O(n²) (and O(n) stack).
Heap sortO(n log n)O(n log n)O(n log n)O(1)NoYesBuild a heap in O(n), then n extractions each sift down log n levels. Guaranteed, but cache-unfriendly so slower than quicksort in practice.
Counting sort (values 0..k)O(n + k)O(n + k)O(n + k)O(n + k)YesNoOne pass to count, one over the k buckets, one to place. No comparisons, so the n log n bound doesn't apply — but k must be small.
Radix sort (LSD, d digits, base b)O(d·(n + b))O(d·(n + b))O(d·(n + b))O(n + b)YesNod stable counting passes, one per digit. For 32-bit ints in base 10, d ≤ 10 — effectively linear.
TimSort (Java objects, List.sort)O(n)O(n log n)O(n log n)O(n)YesNoFinds already-sorted runs (insertion sort for short ones) and merges them. Sorted input is one run → O(n). Merge buffer up to n/2.
Dual-pivot quicksort (Java int[])O(n)O(n log n)O(n log n)O(log n) stack; O(n) when it merges runsNoMostlyTwo pivots split into three parts. Large, nearly sorted arrays are detected as runs and merged (sorted input → O(n)) with a temporary array. Since JDK 14 it also switches to heap sort when partitioning goes too deep, so the worst case is O(n log n).
Selection problems (don't sort everything)
TimeExtra spacewhy
Sort, then indexO(n log n)O(1)–O(n)Simple and safe, but orders n values when you only need one position.
Min-heap of size kO(n log k)O(k)Each of n values costs at most one log k push/pop. Great for streams.
Quickselect (random pivot)O(n) avg, O(n²) worstO(1)Partition like quicksort but keep only one side: n + n/2 + n/4 + … ≈ 2n when pivots land near the middle. Random pivots give O(n) expected (under 3.4n comparisons).

06 · java

Raw vs Collections Framework

Sorting numbers: write it vs call it

javamerge sort by handjava.util.*
class TopDown {    static void sort(int[] a) {        int[] aux = new int[a.length]; // one helper array, reused by every merge        sort(a, aux, 0, a.length - 1);    }     private static void sort(int[] a, int[] aux, int lo, int hi) {        if (lo >= hi) return; // 0 or 1 element is already sorted        int mid = lo + (hi - lo) / 2;        sort(a, aux, lo, mid);       // sort the left half        sort(a, aux, mid + 1, hi);   // sort the right half        merge(a, aux, lo, mid, hi);    }     private static void merge(int[] a, int[] aux, int lo, int mid, int hi) {        for (int k = lo; k <= hi; k++) aux[k] = a[k];        int i = lo, j = mid + 1;     // i walks the left half, j the right half        for (int k = lo; k <= hi; k++) {            if (i > mid) a[k] = aux[j++];               // left used up            else if (j > hi) a[k] = aux[i++];           // right used up            else if (aux[j] < aux[i]) a[k] = aux[j++];  // strict < : ties take left → stable            else a[k] = aux[i++];        }    }}
  • In real code and most interviews, call Arrays.sort — write a sort by hand only when the sort is the question (LC 912) or you need to hook into it (counting inversions).
  • int[] sorts ascending only. For descending, either sort and walk backwards, or box to Integer[] and pass Collections.reverseOrder() (slower: boxing).
  • Collections.sort(list) and list.sort(null) are the same thing: TimSort over the list's array, stable, O(n log n).
  • Objects use a stable sort on purpose: sorting by a second key must not scramble the order from the first.

Custom order: Comparable vs Comparator

javaComparable (natural order)java.util.*
class Natural {    record Version(int major, int minor) implements Comparable<Version> {        @Override        public int compareTo(Version o) {            if (major != o.major) return Integer.compare(major, o.major);            return Integer.compare(minor, o.minor);        }    }}
  • Comparable = the one natural order of a type (compareTo). Comparator = any number of external orders you build on demand.
  • Chain keys with comparing(...).thenComparing(...). Add .reversed() or Comparator.reverseOrder() per key for descending.
  • Prefer comparingInt / comparingLong / comparingDouble — they avoid boxing each key.
  • (a, b) -> a - b silently overflows when values are far apart (e.g. Integer.MIN_VALUE - 1 wraps to a huge positive). Integer.compare never does.
  • A comparator must be consistent (if a < b and b < c then a < c). Breaking that can make TimSort throw "Comparison method violates its general contract!".

Quicksort partitions: Lomuto vs Hoare

javaHoare partition, random pivotjava.util.*
class Hoare {    private static final Random RND = new Random();     static void sort(int[] a) {        quickSort(a, 0, a.length - 1);    }     static void quickSort(int[] a, int lo, int hi) {        if (lo >= hi) return;        int p = partition(a, lo, hi);        quickSort(a, lo, p);      // note: p, not p - 1 — the pivot is not fixed in place        quickSort(a, p + 1, hi);    }     static int partition(int[] a, int lo, int hi) {        int pivot = a[lo + RND.nextInt(hi - lo)]; // random pivot from a[lo..hi-1]        int i = lo - 1, j = hi + 1;        while (true) {            do i++; while (a[i] < pivot);   // find a value that belongs on the right            do j--; while (a[j] > pivot);   // find a value that belongs on the left            if (i >= j) return j;           // pointers crossed: a[lo..j] <= pivot <= a[j+1..hi]            int t = a[i]; a[i] = a[j]; a[j] = t;        }    }}
  • Lomuto (see the simulation): pivot = last element, one pointer collects smaller values. Easiest to get right; the pivot ends in its final slot.
  • Hoare: two pointers walk inward and swap misplaced pairs. About 3× fewer swaps than Lomuto, handles duplicates better — but recurse on [lo, p] and [p+1, hi], not p − 1.
  • Pivot choice decides everything. First/last element on sorted input → O(n²). Random pivot or median-of-three → O(n log n) expected.
  • Many duplicates? Use a 3-way partition (< pivot | = pivot | > pivot) — the Dutch national flag. It's how LC 912 avoids TLE on all-equal arrays.

Heap sort: guaranteed O(n log n) in O(1) space

javain-place heap sortjava.util.*
class InPlaceHeap {    static void sort(int[] a) {        int n = a.length;        // 1. Build a max-heap bottom-up: O(n) in total.        for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);        // 2. Repeatedly move the max (root) to the end and repair the smaller heap.        for (int end = n - 1; end > 0; end--) {            swap(a, 0, end);        // largest value is now final at `end`            siftDown(a, 0, end);    // heap is a[0..end-1]        }    }     private static void siftDown(int[] a, int i, int size) {        while (2 * i + 1 < size) {            int child = 2 * i + 1;                               // left child            if (child + 1 < size && a[child + 1] > a[child]) child++; // pick the bigger child            if (a[i] >= a[child]) return;                        // heap property holds            swap(a, i, child);            i = child;        }    }     private static void swap(int[] a, int i, int j) {        int t = a[i]; a[i] = a[j]; a[j] = t;    }}
  • Turn the array into a max-heap (children of i are 2i+1 and 2i+2), then repeatedly swap the root to the end and sift the new root down.
  • Building the heap bottom-up is O(n), not O(n log n): most nodes are near the bottom and sift down only a little.
  • It's the only common sort with O(n log n) worst case and O(1) extra space — but it's not stable and jumps around memory. See the Heaps chapter for PriorityQueue.

Beyond comparisons: radix sort

javaLSD radix sort (base 10)java.util.*
class Radix {    /** LSD radix sort for non-negative ints: one stable counting pass per decimal digit. */    static void sort(int[] a) {        int max = 0;        for (int x : a) max = Math.max(max, x);        int[] out = new int[a.length];        for (long exp = 1; max / exp > 0; exp *= 10) {   // long: exp * 10 must not overflow            int[] count = new int[10];            for (int x : a) count[(int) (x / exp % 10)]++;            for (int d = 1; d < 10; d++) count[d] += count[d - 1];            for (int i = a.length - 1; i >= 0; i--) out[--count[(int) (a[i] / exp % 10)]] = a[i];            System.arraycopy(out, 0, a, 0, a.length);        }    }}
  • Radix sort runs a stable counting sort on each digit, least significant first. Stability is what keeps earlier digits' order intact.
  • Use it for many fixed-width keys (ints, IDs, fixed-length strings). Negatives need an offset or a separate pass.
  • In interviews, radix sort is usually a talking point ("can you beat n log n?"); counting sort is the one you'll actually code.
Java API you will actually use
calldoescost
Arrays.sort(int[] a)Ascending, in place (dual-pivot quicksort)O(n log n)
Arrays.sort(int[] a, from, to)Sorts only a[from..to-1]O(m log m), m = to − from
Arrays.sort(T[] a, Comparator)Stable sort of objects (TimSort)O(n log n)
Collections.sort(list) / list.sort(cmp)Stable sort of a List (TimSort)O(n log n)
Comparator.comparingInt(f).thenComparing(g)Sort by f, break ties with gO(1) per compare
Comparator.reverseOrder() / cmp.reversed()Descending orderO(1) per compare
Integer.compare(a, b)Overflow-safe -1/0/1 comparisonO(1)
Arrays.parallelSort(a)Multi-threaded sort for very large arraysO(n log n) work
list.stream().sorted(cmp).toList()Sorted copy, original untouchedO(n log n)

Just sort numbers

→ Arrays.sort(int[])

Fastest option in the JDK; stability is meaningless for primitives.

Sort objects by several fields

→ list.sort(comparing(..).thenComparing(..))

Stable TimSort plus readable, overflow-safe comparators.

Descending ints

→ Sort ascending then read backwards (or Integer[] + reverseOrder())

int[] has no comparator overload; boxing costs memory and time.

Values in a small range (ages, grades, 0–2 colours)

→ Counting sort

O(n + k) beats O(n log n) when k is small.

Sort a linked list

→ Merge sort

No random access needed; O(1) extra space bottom-up.

Only the k-th / top k elements

→ Quickselect or a size-k heap

O(n) average / O(n log k) — no need to sort everything.

Guaranteed O(n log n) with O(1) extra memory

→ Heap sort

Merge needs O(n) memory; quicksort has an O(n²) worst case.

07 · recognise

Spot the pattern

Intervals, meetings, schedules — anything with start/end

Sort by start (or end), then sweep once

"Find duplicates / closest pair / group equal things"

Sort so equal or near values become neighbours

Pair or triplet sums without needing original indices

Sort + two pointers

"k-th largest / smallest", "top k"

Quickselect (O(n) avg) or a size-k heap (O(n log k))

Values come from a small known range (0–100, three colours, lowercase letters)

Counting sort / buckets in O(n + k)

"Arrange to form the largest/smallest…", custom ordering rule

Custom comparator — prove the rule is transitive

Count pairs i < j with some order condition (inversions, reverse pairs)

Merge sort and count during the merge

Sort a linked list in O(n log n)

Merge sort (slow/fast split + merge)

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

  • Comparator (a, b) -> a - b overflows for large or negative values. Use Integer.compare or comparingInt.
  • Arrays.sort(int[], Collections.reverseOrder()) doesn't compile — comparators only work on object arrays like Integer[].
  • Assuming quicksort is always O(n log n). Fixed first/last pivots on sorted input — or naive partitions on all-equal input — make it O(n²).
  • Hoare partition with quickSort(lo, p - 1): the pivot isn't fixed at p in Hoare, so you lose elements or loop forever. Use [lo, p] and [p + 1, hi].
  • Merge with <= vs < mixed up: taking the right element on ties breaks stability.
  • Allocating a new helper array in every merge call — O(n log n) garbage. Allocate once and pass it down.
  • Sorting when the problem needs the original indices — sort an index array or pairs instead, or use a HashMap.
  • Counting sort on a huge range (values up to 10⁹) — the count array alone would blow memory.

tricks

  • First question in any array problem: "Would sorting help, and can I afford O(n log n)?" It often turns O(n²) into O(n log n).
  • Say the trade-off in one line: "merge sort — stable, guaranteed, O(n) memory; quicksort — in-place, faster in practice, O(n²) worst."
  • Know insertion sort cold: it's the base case inside TimSort and introsort, and the answer to "what's best for nearly-sorted data?"
  • When writing a comparator, test it on three values a < b < c in your head — transitivity bugs are silent until production.
  • For "k-th largest", mention all three: sort (simple), heap (streaming), quickselect (optimal average) — then code the one they want.
  • Memorise the merge loop with the four cases (left empty, right empty, right smaller, else left). It powers sort, inversion counting and merge-k-lists.

09 · why & how

Questions you might be too shy to ask

Why can't any comparison sort beat O(n log n)?

Each comparison is a yes/no question. There are n! possible orders of n items, and every one must lead to a different answer, so you need at least log₂(n!) questions. log₂(n!) ≈ n log₂ n − 1.44n, which is Θ(n log n). Counting and radix sort escape this by not comparing at all.

If quicksort's worst case is O(n²), why is it so popular?

Because the worst case almost never happens with random (or median-of-three) pivots, and in the average case it does fewer memory moves and has great cache locality. Libraries also add guards: since JDK 14, OpenJDK's dual-pivot quicksort falls back to heap sort if partitioning goes too deep.

What does "stable" actually change for me?

Sort people by name, then stably by age: people of the same age stay in name order. With an unstable sort, that name order could be scrambled. For plain ints stability is invisible — that's why Java uses an unstable algorithm for int[] but a stable one for objects.

What does a comparator's return value mean? I always mix up which way is ascending.

compare(a, b) returns a negative number when a should come first, 0 for a tie, and a positive number when b should come first. Integer.compare(a, b) gives ascending: [5, 2, 9] → [2, 5, 9]. Swap the arguments, Integer.compare(b, a), and you get descending. Bas itna yaad rakho: negative means "a goes first".

Arrays.sort(nums) gave nothing back and my original order is gone. How do I keep the original indices?

Arrays.sort returns void: it sorts the same array in place, so the old order is lost. Need an untouched copy? Sort nums.clone() instead. Need each value's original index? Build pairs — for each i, p[i] = new int[]{nums[i], i} — then Arrays.sort(p, (x, y) -> Integer.compare(x[0], y[0])). This compiles because each row of an int[][] is an object (an int[]), so the comparator overload accepts it. The same trick sorts intervals by their start.

Why is insertion sort used inside "fast" sorts?

For tiny ranges its low overhead beats the recursion and bookkeeping of merge/quick sort. In the JDK 17 source, TimSort (used for objects) sorts pieces under 32 elements with binary insertion sort. The dual-pivot quicksort (used for int[]) switches to insertion sort once a part is a few dozen elements long — 44 or more, depending on where the part sits. These cut-offs are OpenJDK implementation details, not part of the Java spec.

Is merge sort in-place?

Not on arrays — the standard merge needs an O(n) helper array. On linked lists it is: merging just relinks nodes, so bottom-up merge sort uses O(1) extra space.

Why does merge sort split into [lo, mid] and [mid + 1, hi], and not [lo, mid - 1] and [mid, hi]?

mid = lo + (hi - lo) / 2 rounds down, so with two elements (lo = 0, hi = 1) you get mid = 0. [lo, mid] and [mid + 1, hi] give [0, 0] and [1, 1]: both are smaller, so the recursion reaches the base case lo >= hi. The other split gives [0, -1] and [0, 1] — the right part is the whole range again, so it recurses until StackOverflowError. Rule: when mid rounds down, mid belongs to the left half.

I understand merge sort when I read it, but I get lost in the recursion when I dry-run or write it. What now?

Don't trace every level. Trust that the two recursive calls hand back sorted halves — the leap of faith from the Recursion chapter. Then only one thing must be right: the merge of two sorted halves with pointers i, j and k. Practise that merge alone on paper, [2, 5] + [1, 9] → [1, 2, 5, 9], until it feels boring. Then wrap it in the skeleton (base case, mid, two calls, merge) and write it from a blank file again the next day — recall, not re-reading, is what makes it stick.

In the Lomuto partition, what do i and j mean, and why does the loop stop at j < hi?

The pivot sits at a[hi], so j scans every other value — that's why j < hi. i marks where the next smaller value goes: a[lo..i-1] are all smaller than the pivot. When a[j] < pivot, swap it into slot i and grow the zone with i++. At the end, swap the pivot into slot i: smaller values on its left, the rest on its right. Try [3, 8, 1, 5] (pivot 5) in the sim: 3 and 1 end up in the left zone, and 5 lands at index 2 — final forever.

When should I use counting sort?

When values are integers in a small range k (like 0–100 or 26 letters) and k is not much bigger than n. Then O(n + k) beats O(n log n). If k is huge (values up to 10⁹), the count array is too big.

In Largest Number, why is comparing strings with compareTo safe? As strings, isn't "9" bigger than "10"?

Yes — comparing "9" with "10" directly would be wrong as numbers. But we never do that: we compare a + b with b + a, and those two strings always have the same length. For equal-length digit strings, dictionary order equals numeric order: "910" vs "109" differ first at '9' vs '1', so 910 wins. No parsing needed — and parsing would overflow anyway, since two 10-digit pieces glue into 20 digits, more than a long holds.

Which sort should I write when the interviewer says "don't use the library"?

Merge sort: it's always O(n log n), its code is short and easy to get right, and there's no worst-case trap. Mention randomized quicksort (in-place, faster in practice) and heap sort (O(1) space) as alternatives.

Do I have to memorize all these sorts?

Know how each works and its trade-offs (the big table). Be able to code merge sort, quicksort partition, and insertion sort from scratch. Bubble and selection are mainly for understanding — nobody uses them in production.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run.

  1. #912
    Sort an Arraymust-do
    MediumGoogleAmazonMicrosoft
  2. #179
    Largest Numbermust-do
    MediumAdobeAmazonMicrosoftGoogle
  3. #148
    Sort Listmust-do
    MediumByteDance / TikTokAmazonMicrosoftMeta
  4. #274
    H-Index
    MediumBloombergGoogleAmazonMeta
  5. #493
    Reverse Pairs
    HardAmazonGoogle
  6. #324
    Wiggle Sort II
    MediumGoogleAmazon
  7. #1636
    Sort Array by Increasing Frequency
    EasyAdobeAmazon

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

  1. #56
    Merge Intervals
    Mediumin Intervals

    Sorting by start turns an O(n²) pair search into one linear sweep — sort first to expose structure.

  2. #215
    Kth Largest Element in an Array
    Mediumin Heaps

    Quickselect is quicksort's partition recursing into one side only: O(n) average (see its quickselect dry run).

  3. #75
    Sort Colors
    Mediumin Two Pointers

    Counting sort for three keys, and the 3-way partition at the heart of 3-way quicksort.

11 · revise

The whole chapter on one screen

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

  1. what it is

    Sorting puts equal and nearby values next to each other, so duplicates, overlaps and gaps show up in one linear scan.

  2. use it when

    Intervals, duplicates, closest pairs, pair sums without indices, "form the largest…": ask first — would sorting expose the structure?

  3. cost

    Comparison sorts can't beat Ω(n log n). Merge/heap: O(n log n) always. Quicksort: O(n log n) expected, O(n²) worst. Counting: O(n + k).

  4. template

    Numbers: Arrays.sort(nums). Objects: list.sort(comparingInt(f).thenComparing(g)) — stable TimSort keeps earlier orders as tie-breakers.

  5. trap

    (a, b) -> a - b overflows: MIN_VALUE - 1 wraps to a big positive. Use Integer.compare(a, b) or Comparator.comparingInt.

  6. trap

    A fixed first/last pivot makes quicksort O(n²) on sorted input; a 2-way partition crawls on all-equal input. Random pivot + 3-way split fixes both.

  7. trap

    int[] takes no comparator. For descending ints, sort and read backwards, or box to Integer[] with Collections.reverseOrder().

  8. pro tip

    Only the k-th or top k? Don't sort everything: quickselect is O(n) on average, a size-k heap is O(n log k).

  9. pro tip

    Sorting a linked list? Merge sort: no random access needed, and merging only relinks nodes — O(1) extra space bottom-up.

12 · recall

Flip, remember, repeat

card 1 / 14
recall

Why can't any comparison sort beat O(n log n) in the worst case?

tap or Space to flip ↻

Question 1: Why can't any comparison sort beat O(n log n) in the worst case?

13 · check yourself

Quick quiz

  1. Which sort is fastest on an array that is already sorted?

  2. You sort employees by name, then by department with a stable sort. Inside one department, how are they ordered?

  3. What does `Arrays.sort(int[])` use in modern Java?

  4. Why is `(a, b) -> a - b` a dangerous comparator?

  5. Merge sort's extra space on an array is…

  6. Values are integers from 0 to 100 and n = 10⁶. Best choice?

  7. When does quicksort hit its O(n²) worst case?

  8. Quickselect finds the k-th largest element in…

0/0 correct · 8 left

14 · learn more

A second teacher, if you want one