Visualized DSA Strategies

Episode 7 Sorting

1 h 9 min · PHP · Quiz

Title card of Episode 7: Sorting

▶ This video is coming to YouTube soon.

The complete guide to sorting for coding interviews, in PHP. 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 PHP with sort, usort and the spaceship operator (in place, returning true, stable since PHP 8.0), 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 why every PHP sort is stable since PHP 8.0
  • 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, rsort, usort with <=>, asort, ksort and array_multisort, and why an in-place function takes &$nums
  • 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:30What sorting unlocks
  5. 2:16What each sort costs
  6. 3:19Insertion sort: 28 comparisons
  7. 3:46Merge sort: 12 comparisons
  8. 4:10Why O(n log n)?
  9. 4:48Sorting in PHP
  10. 6:27Five traps
  11. 7:35Nine sorting techniques
  12. 8:15Type 1 · Sort a nearly sorted array
  13. 14:12Type 2 · Sort an array in O(n log n)
  14. 21:32Type 3 · K-th largest number
  15. 28:19Type 4 · Sort small numbers
  16. 34:42Type 5 · Numbers two arrays share
  17. 41:07Type 6 · Smallest gap between two numbers
  18. 47:13Type 7 · Merge overlapping intervals
  19. 54:31Type 8 · H-index
  20. 1:00:08Type 9 · Count inversions
  21. 1:06:38Spot the technique
  22. 1:07:26Quiz: which technique?
  23. 1:08:14Recap

Quiz: test yourself

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