Sorting

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.

   #1
2. ↯use it when

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

   #2
3. O( )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).

   #3
4. { }template

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

   #4
5. !trap

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

   #5
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.

   #6
7. !trap

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

   #7
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).

   #8
9. ✦pro tip

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

   #9

Shaky on a card? Open the chapter or flip its recall cards.