Visualized DSA Strategies

Episode 7 Sorting

1 h 7 min · Python · Quiz

Title card of Episode 7: Sorting

▶ This video is coming to YouTube soon.

The complete guide to sorting for coding interviews, in Python. 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 list.sort and sorted work (Timsort: stable, and O(n) on data already in order), sorting anything with a key function and tuples instead of 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
  • list.sort vs sorted, key functions and tuple keys, reverse=True, cmp_to_key, heapq.nsmallest and bisect.insort
  • 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:24What sorting unlocks
  5. 2:10What each sort costs
  6. 3:10Insertion sort: 28 comparisons
  7. 3:37Merge sort: 12 comparisons
  8. 4:01Why O(n log n)?
  9. 4:38Sorting in Python
  10. 6:10Five traps
  11. 7:09Nine sorting techniques
  12. 7:49Type 1 · Sort a nearly sorted array
  13. 13:42Type 2 · Sort an array in O(n log n)
  14. 20:40Type 3 · K-th largest number
  15. 27:11Type 4 · Sort small numbers
  16. 33:33Type 5 · Numbers two arrays share
  17. 39:44Type 6 · Smallest gap between two numbers
  18. 45:31Type 7 · Merge overlapping intervals
  19. 52:21Type 8 · H-index
  20. 58:01Type 9 · Count inversions
  21. 1:04:44Spot the technique
  22. 1:05:29Quiz: which technique?
  23. 1:06:17Recap

Quiz: test yourself

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