Sorting a big pile of exam papers: split it between two helpers, let each sort their half, then merge the two sorted piles.
Clues that point here
→ Sorting
→ Counting inversions
→ The answer for a range can be built from its halves
→ O(n log n) expected
Not this pattern when
✕ The halves overlap heavily (DP)
✕ A single pass suffices
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Divide and Conquer · template
void mergeSort(int[] a, int lo, int hi) {
if (lo >= hi) return;
int mid = (lo + hi) >>> 1;
mergeSort(a, lo, mid);
mergeSort(a, mid + 1, hi);
merge(a, lo, mid, hi); // combine two sorted halves
}