Framework #13 — Merge sort vs quicksort vs binary search patterns

DIVIDE & CONQUER — PATTERN SELECTION
─────────────────────────────────────
MERGE SORT PATTERN:
  Split → recurse both halves → merge results
  □ Stable sort
  □ Count inversions (merge step counts cross-pairs)
  □ Merge K sorted lists
  □ External sorting (fits on disk)
  Time: O(n log n), Space: O(n)

QUICKSORT / PARTITION PATTERN:
  Pick pivot → partition → recurse halves
  □ Quickselect: find kth element in O(n) avg
  □ Dutch national flag (3-way partition)
  □ In-place sort (O(log n) space)
  Time: O(n log n) avg, O(n^2) worst

BINARY SEARCH PATTERN:
  Check mid → discard half → repeat
  □ Search sorted array
  □ Search on answer (min/max feasible)
  □ Find peak, rotation point
  Time: O(log n)

DECISION:
  Need stable sort / merge?     → merge sort pattern
  Need kth element / partition? → quickselect pattern
  Search space halves each step?→ binary search
  "Count cross-half pairs"?     → merge sort merge step