Sorting, Selection & Divide-and-Conquer

• Quicksort = partition + recurse
• Quickselect = partition + one side
• Merge sort = split + merge
• Combine step is where counting happens

Partition

• Choose pivot (random is safest)
• < pivot on left, > pivot on right
• Pivot ends in its final index

Quickselect

• If pivot index == k-1, done
• Else recurse only into the side that contains k
• Average O(n)

Merge + Inversions

• When left[i] > right[j], add (len(left)-i)
• Works for many pair-counting tasks

Divide-and-conquer pattern

• Base case
• Split
• Recurse
• Combine (the real work)