Visualized DSA Strategies

Episode 7 Sorting

1 h 7 min · JavaScript · Quiz

Title card of Episode 7: Sorting

▶ This video is coming to YouTube soon.

The complete guide to sorting for coding interviews, in JavaScript. 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 JavaScript (with no comparator, sort compares items as strings; V8's sort is TimSort: stable, in place, and O(n) on data already in order), comparators that return a number, 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
  • sort with a comparator (a − b, never the default string order), copying first with a spread or toSorted, ties with ||, localeCompare and typed arrays
  • 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:24What sorting does
  3. 0:55Stable sorts
  4. 1:30What sorting unlocks
  5. 2:16What each sort costs
  6. 3:18Insertion sort: 28 comparisons
  7. 3:45Merge sort: 12 comparisons
  8. 4:08Why O(n log n)?
  9. 4:46Sorting in JavaScript
  10. 6:33Five traps
  11. 7:37Nine sorting techniques
  12. 8:17Type 1 · Sort a nearly sorted array
  13. 14:05Type 2 · Sort an array in O(n log n)
  14. 20:57Type 3 · K-th largest number
  15. 27:30Type 4 · Sort small numbers
  16. 33:53Type 5 · Numbers two arrays share
  17. 40:15Type 6 · Smallest gap between two numbers
  18. 46:05Type 7 · Merge overlapping intervals
  19. 52:57Type 8 · H-index
  20. 58:40Type 9 · Count inversions
  21. 1:05:13Spot the technique
  22. 1:05:59Quiz: which technique?
  23. 1:06:46Recap

Quiz: test yourself

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