Order and position
Episode 7 Sorting
▶ This video is coming to YouTube soon.
The complete guide to sorting for coding interviews, in Java. First the theory: what sorted and stable mean, what sorting unlocks, what every classic sort costs, why the fast ones are O(n log n), how to sort anything in Java with comparators, and five traps. Then nine techniques, each worked as a small problem in full: examples, the brute force animated beside the running line of code, the complete code, every line explained, and the better solution the same way.
What you'll learn
- Sorted and stable: what they mean and when stability matters
- Bubble, selection, insertion, merge, quick, heap and counting sort, and what each costs
- Why merge sort is O(n log n): log n levels of n work
- Arrays.sort, Collections.sort, comparators, comparingInt and thenComparing
- Insertion sort on nearly sorted input, and merge sort step by step
- Partition and quickselect for the k-th largest in O(n) on average
- Counting sort: O(n + k) with no comparisons
- Sort first: two pointers, neighbour checks, interval sweeps, sort-and-scan
- Counting inversions while merge sorting
Chapters
- 0:00Intro
- 0:21What sorting does
- 0:51Stable sorts
- 1:18What sorting unlocks
- 2:03What each sort costs
- 2:47Insertion sort: 28 comparisons
- 3:14Merge sort: 12 comparisons
- 3:38Why O(n log n)?
- 4:16Sorting in Java
- 5:19Five traps
- 5:56Nine sorting techniques
- 6:36Type 1 · Sort a nearly sorted array
- 12:19Type 2 · Sort an array in O(n log n)
- 18:47Type 3 · K-th largest number
- 24:55Type 4 · Sort small numbers
- 31:06Type 5 · Numbers two arrays share
- 37:07Type 6 · Smallest gap between two numbers
- 42:50Type 7 · Merge overlapping intervals
- 49:15Type 8 · H-index
- 54:46Type 9 · Count inversions
- 1:00:58Spot the technique
- 1:01:44Quiz: which technique?
- 1:02:31Recap
Quiz: test yourself
The 5 questions from the end of the episode. Pick an answer to see why it's right.