Visualized DSA Strategies

Episode 7 Sorting

1 h 6 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 to sort anything in C# with Array.Sort, comparison lambdas and LINQ (and why Array.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
  • Array.Sort and List.Sort (introsort, not stable), CompareTo lambdas, OrderBy and ThenBy, Array.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:22What sorting does
  3. 0:52Stable sorts
  4. 1:30What sorting unlocks
  5. 2:15What each sort costs
  6. 3:15Insertion sort: 28 comparisons
  7. 3:42Merge sort: 12 comparisons
  8. 4:05Why O(n log n)?
  9. 4:43Sorting in C#
  10. 6:27Five traps
  11. 7:19Nine sorting techniques
  12. 7:59Type 1 · Sort a nearly sorted array
  13. 13:46Type 2 · Sort an array in O(n log n)
  14. 20:23Type 3 · K-th largest number
  15. 26:47Type 4 · Sort small numbers
  16. 33:06Type 5 · Numbers two arrays share
  17. 39:15Type 6 · Smallest gap between two numbers
  18. 45:02Type 7 · Merge overlapping intervals
  19. 52:01Type 8 · H-index
  20. 57:33Type 9 · Count inversions
  21. 1:03:49Spot the technique
  22. 1:04:33Quiz: which technique?
  23. 1:05:21Recap

Quiz: test yourself

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