Count of Smaller Numbers After Self

Count of Smaller Numbers After Self asks a counting question that looks like it needs O(n²) brute force, but a tiny tweak to merge sort answers it in O(n log n). The trick: the merge step already tells you, for free, when a number is smaller than ones that came before it.

The slow way first

The obvious approach: for each index i, scan everything to its right and count how many are smaller. Two nested loops, O(n²). For n up to tens of thousands that is far too slow.

The question to ask: what natural process compares an element against many later elements at once? Sorting does — and merge sort compares a left half against a right half in exactly the right direction.

The idea: count during the merge

Sort (value, index) pairs with merge sort. The key moment is the merge of two already-sorted halves. Because the left half sits entirely before the right half in the original array, whenever you pull an element from the right run and it is smaller than the left elements still waiting, every one of those waiting left elements has just discovered one more smaller-number-to-its-right. Bump each of their counts by one — using their original indices so the answer lands in the right slot.

We carry the original index alongside each value so that the bump always updates the correct entry of the final answer array, no matter how the values get shuffled by sorting.

Walk through it

Step through the animation. Two sorted runs are shown: left holds 2, 5 (original indices 1, 0) and right holds 1, 6 (original indices 3, 2). When 1 from the right is placed before the whole left run, both waiting left items get +1. The rest of the merge takes from the left, so no further credit is given. This single merge produces count = [1, 1, 0, 0]; deeper merges add the remaining counts.

Pseudocode

merge sort the (value, index) pairs:
  recursively sort left and right halves
  while merging the two sorted runs:
    if the next left value is <= the next right value:
      place the left element (no counting)
    else:
      # this right element is smaller than every left element still waiting
      for each left element not yet placed:
        count[that element's original index] += 1
      place the right element
return count

The Python solution

def merge(arr, lo, mid, hi, count):
    left = arr[lo:mid + 1]      # (value, index) pairs
    right = arr[mid + 1:hi + 1]
    i = j = 0
    for k in range(lo, hi + 1):
        if j >= len(right) or (i < len(left) and left[i][0] <= right[j][0]):
            arr[k] = left[i]
            i += 1
        else:
            # right[j] jumped ahead of len(left) - i left items
            for p in range(i, len(left)):
                count[left[p][1]] += 1
            arr[k] = right[j]
            j += 1
    return count

• arr holds (value, index) pairs; the second field is the original position so credits land in the right slot.
• left and right are the two already-sorted runs; i and j walk them.
• Line 6 is the stable-merge condition: take from the left when its value is <= the right value (the <= keeps equal values from being miscounted, since equal is not smaller).
• Lines 9–12 are the heart: when we take from the right, every left element from i onward is larger and sits earlier, so each gets +1 on its original index.
• The driver (not shown) recursively halves the array and calls merge, accumulating into the shared count.

Complexity

We pay O(n) extra space for the pair array and merge buffers, and the inner credit loop is absorbed into the linear merge, so the total stays O(n log n).

When this pattern shows up

Practice