templates · Linked lists, sorting & selection

Merge sort (and counting while you merge)

  • "Sort an array" with a guaranteed O(n log n), even in the worst case
  • Count pairs i < j with a rule like nums[i] > 2 * nums[j], or "smaller numbers after self"
  • Merge two (or k) sorted runs: arrays or linked lists

Merge sort & merging sorted runsDivide and conquer

the one rule

The invariant

When merge(lo, mid, hi) runs, a[lo..mid] and a[mid+1..hi] are each sorted.

write it from memory

The template

merge sort with one buffer

javajava.util.*
/** Sorts nums in place. One temp buffer is shared by every merge. */static void mergeSort(int[] nums) {    sort(nums, new int[nums.length], 0, nums.length - 1);} static void sort(int[] a, int[] tmp, int lo, int hi) {    if (lo >= hi) return;                         // 0 or 1 element: already sorted    int mid = lo + (hi - lo) / 2;    sort(a, tmp, lo, mid);                        // sort the left half    sort(a, tmp, mid + 1, hi);                    // sort the right half    // both halves are sorted here: count cross pairs now, if the problem asks    merge(a, tmp, lo, mid, hi);} static void merge(int[] a, int[] tmp, int lo, int mid, int hi) {    int i = lo, j = mid + 1, k = lo;    while (i <= mid && j <= hi) {        if (a[i] <= a[j]) tmp[k++] = a[i++];      // <= keeps equal values in order (stable)        else tmp[k++] = a[j++];    }    while (i <= mid) tmp[k++] = a[i++];           // copy what is left    while (j <= hi) tmp[k++] = a[j++];    System.arraycopy(tmp, lo, a, lo, hi - lo + 1);}

Make the buffer once in the entry method. Making a new array in every merge is correct but slow.

fill in the blanks — only these lines change per problem

  1. line 11The hook for counting problems: between the two recursive calls and the merge, the halves are sorted.
  2. line 18Which side to take first. <= keeps it stable; flip it for a descending sort.

count cross pairs before merging

javajava.util.*
/** The same skeleton, counting reverse pairs: i < j and nums[i] > 2 * nums[j]. */static int reversePairs(int[] nums) {    return countSort(nums, new int[nums.length], 0, nums.length - 1);} static int countSort(int[] a, int[] tmp, int lo, int hi) {    if (lo >= hi) return 0;    int mid = lo + (hi - lo) / 2;    int count = countSort(a, tmp, lo, mid) + countSort(a, tmp, mid + 1, hi);    for (int i = lo, j = mid + 1; i <= mid; i++) {           // both halves sorted: one sweep        while (j <= hi && a[i] > 2L * a[j]) j++;             // long: 2 * a[j] can overflow        count += j - (mid + 1);    }    merge(a, tmp, lo, mid, hi);    return count;}

Both halves are sorted, so one pointer j only moves forward. That makes the count O(n) per merge instead of O(n²).

fill in the blanks — only these lines change per problem

  1. line 11The pair rule you count, e.g. a[i] > 2L * a[j]. Use long when the rule multiplies.
  2. line 10How the count is gathered: here, for each left element, how many right elements satisfy the rule.

complexity

What it costs

time O(n log n)
The array is halved about log₂ n times, and each level of merges touches all n elements once. The counting sweep adds O(n) per level, so the total stays the same.
space O(n)
One temp buffer of size n, shared by every merge, plus O(log n) for the recursion.

watch out

Common bugs

  • mid = (lo + hi) / 2 overflows when lo and hi are near Integer.MAX_VALUE. Use lo + (hi - lo) / 2.
  • Forgetting to copy the leftovers of one half, so the tail of the range is lost.
  • Counting inside the merge loop with a rule that is not the merge order (like > 2 * x). Count in a separate sweep first.

use it

Practise it on

learn it properly