Visualized DSA Strategies

Episode 7 Sorting

1 h 9 min · Go · Quiz

Title card of Episode 7: Sorting

▶ This video is coming to YouTube soon.

The complete guide to sorting for coding interviews, in Go. 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 Go with slices.Sort, compare functions and sort.Slice (and why slices.Sort isn't stable), 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
  • slices.Sort and sort.Ints (pdqsort, not stable), slices.SortFunc with cmp.Compare, sort.Slice, slices.SortStableFunc, slices.BinarySearch
  • 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

  1. 0:00Intro
  2. 0:21What sorting does
  3. 0:52Stable sorts
  4. 1:30What sorting unlocks
  5. 2:16What each sort costs
  6. 3:17Insertion sort: 28 comparisons
  7. 3:45Merge sort: 12 comparisons
  8. 4:08Why O(n log n)?
  9. 4:46Sorting in Go
  10. 6:30Five traps
  11. 7:37Nine sorting techniques
  12. 8:16Type 1 · Sort a nearly sorted array
  13. 14:23Type 2 · Sort an array in O(n log n)
  14. 21:37Type 3 · K-th largest number
  15. 28:05Type 4 · Sort small numbers
  16. 34:31Type 5 · Numbers two arrays share
  17. 41:00Type 6 · Smallest gap between two numbers
  18. 46:56Type 7 · Merge overlapping intervals
  19. 54:18Type 8 · H-index
  20. 59:53Type 9 · Count inversions
  21. 1:06:48Spot the technique
  22. 1:07:39Quiz: which technique?
  23. 1:08:27Recap

Quiz: test yourself

The 5 questions from the end of the episode. Pick an answer to see why it's right.