Visualized DSA Strategies

Episode 7 Sorting

1 h 9 min · C++ · Quiz

Title card of Episode 7: Sorting

▶ This video is coming to YouTube soon.

The complete guide to sorting for coding interviews, in C++. 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 std::sort (introsort, not stable) and std::stable_sort work, comparators as lambdas that must be a strict less-than, 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
  • std::sort vs stable_sort, lambda comparators (<, never <=), pairs and tuples, nth_element, partial_sort and lower_bound
  • 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:25What sorting does
  3. 0:55Stable sorts
  4. 1:29What sorting unlocks
  5. 2:15What each sort costs
  6. 3:25Insertion sort: 28 comparisons
  7. 3:52Merge sort: 12 comparisons
  8. 4:15Why O(n log n)?
  9. 4:53Sorting in C++
  10. 6:49Five traps
  11. 7:41Nine sorting techniques
  12. 8:21Type 1 · Sort a nearly sorted array
  13. 14:27Type 2 · Sort an array in O(n log n)
  14. 21:49Type 3 · K-th largest number
  15. 28:31Type 4 · Sort small numbers
  16. 34:54Type 5 · Numbers two arrays share
  17. 41:30Type 6 · Smallest gap between two numbers
  18. 47:40Type 7 · Merge overlapping intervals
  19. 55:05Type 8 · H-index
  20. 1:00:43Type 9 · Count inversions
  21. 1:07:17Spot the technique
  22. 1:08:02Quiz: which technique?
  23. 1:08:50Recap

Quiz: test yourself

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