Counting inversions
Count the pairs of items that are in the wrong order, in O(n log n), by counting during merge sort's merge step.
O(n log n)Space O(n)6 practice problemsStep-through pictureThe idea
An inversion is a pair of positions i < j where items[i] > items[j]: a bigger item sits before a smaller one. A sorted list has zero inversions. A list in reverse order has the most, n × (n - 1) / 2. So the number of inversions measures how unsorted a list is.
Checking every pair takes O(n²) time. Merge sort can count them in O(n log n). The trick is in the merge step. When an item from the right half is taken before some items still waiting in the left half, each of those waiting items is bigger than it and was before it in the list: each one is an inversion.
So each time the merge takes from the right half, add the number of items left in the left half, left.length - i. Add up these numbers at every level, plus the inversions inside each half, and you have the total.
An everyday example
Counting who cut in line
Two lines of people, each already ordered by ticket number, are being merged into one line, smallest ticket first. Every time someone from the second line steps ahead of people still waiting in the first line, each of those waiting people has a bigger ticket but was standing earlier. Each of them makes one wrong-order pair with the person who stepped ahead. Counting the people still waiting at that moment counts all of those pairs at once.
| In the example | In the code |
|---|---|
| The two ordered lines | The sorted halves left.sorted and right.sorted |
| Someone from the second line steps ahead | Taking right.sorted[j] |
| People still waiting in the first line | left.sorted.length - i |
| Adding them to the tally | count += left.sorted.length - i |
From the slow way to counting inversions
- An inversion is a pair of positions
i < jwithitems[i] > items[j]. The obvious way to count them is to check every pair with two nested loops. That isn × (n - 1) / 2checks: about 5 billion for 100,000 items, far too slow. - Split the list into a left half and a right half. Every inversion is one of three kinds: both items in the left half, both in the right half, or one in each, with the bigger one on the left. The first two kinds are the same problem on smaller lists, so recursion can count them.
- The cross pairs are the hard part. Here is the useful fact: a cross pair only cares about which half each item is in, not where inside it. So we may sort each half without changing the number of cross pairs. And with both halves sorted, cross pairs are easy to count in one pass.
- During a merge of the sorted halves, when
right.sorted[j]is taken before the left itemleft.sorted[i], it is smaller than that item and everything after it inleft. Thoseleft.sorted.length - iitems all formed a cross pair with it. So merge sort, plus one addition each time the right side wins, counts every inversion. That is counting inversions with merge sort.
How it works
- If the list has 0 or 1 items, it has no inversions: return it with
count = 0. - Split at the middle and recursively count the inversions inside each half; each call also returns its half sorted.
- Start
countat the sum of the two halves' counts. - Merge the sorted halves. When
left.sorted[i] <= right.sorted[j], take the left item; no new inversions. - When the right item is smaller, every remaining left item (
left.sorted.length - iof them) forms an inversion with it. Add that tocountand take the right item. - Return the merged list and
count.
Watch it run
This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.
See every step at onceThe same run, laid out side by side
The code
Point at a note to light up the lines it explains.
function countInversions(items) {if (items.length <= 1) return { sorted: items, count: 0 };const middle = Math.floor(items.length / 2);const left = countInversions(items.slice(0, middle));const right = countInversions(items.slice(middle));const sorted = [];let count = left.count + right.count;let i = 0;let j = 0;while (i < left.sorted.length && j < right.sorted.length) {if (left.sorted[i] <= right.sorted[j]) {sorted.push(left.sorted[i++]);} else {count += left.sorted.length - i;sorted.push(right.sorted[j++]);}}sorted.push(...left.sorted.slice(i), ...right.sorted.slice(j));return { sorted, count };}
How fast it is
| Time | O(n log n) |
|---|---|
| Extra memory | O(n) |
It is merge sort with one addition per merge step: about log n levels, each touching all n items once. The merged arrays use O(n) memory.
- Best case
O(n log n)Even a sorted list like
[1, 2, 3, 4], with zero inversions, is split and merged at every level. - Average case
O(n log n)Any order:
log₂ nlevels of merging, each touching allnitems once, with one extra addition per step. - Worst case
O(n log n)A reversed list has the most inversions,
n × (n - 1) / 2, but the cost doesn't grow with the count, because each addition counts many pairs at once.
Common mistakes
- Adding
1instead ofleft.sorted.length - iwhen taking from the right. Each right item can form inversions with many waiting left items. - Using
<instead of<=, which counts equal pairs as inversions. - Counting while merging, then forgetting to add the halves' own counts.
- Counting a different relation, such as
items[i] > 2 × items[j], inside the same merge loop. That condition needs its own pass with a separate pointer before the merge, because it does not follow the merge order.
When to use it
Look for these clues in a problem:
- The question asks how many pairs are out of order, or how far a list is from sorted.
- It asks for the number of adjacent swaps needed to sort (that is exactly the inversion count).
- It compares two rankings and asks how many pairs they order differently.
- It counts pairs
i < jwith some relation betweenitems[i]anditems[j], likeitems[i] > 2 × items[j].
Check yourself
Answer each one in your head first, then open it.
Why is it safe to sort each half before counting cross pairs?
A cross pair only depends on which half each item is in and which is bigger. Sorting inside a half moves items within it, so it doesn't change any cross pair.
Why add left.sorted.length - i and not 1 when a right item is taken?
Every left item from i to the end is bigger than the right item, because left.sorted is sorted. Each of them forms a separate inversion with it.
How many inversions does [2, 1, 4, 3, 6, 5] have?
Three: (2, 1), (4, 3), and (6, 5). Every other pair is in order.
What would the code count if the merge used < instead of <=?
Equal pairs: on a tie it would take the right item and add the waiting left items, including the equal one. [3, 3] would wrongly report one inversion.
Practice problems
Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.
0 of 6 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.
Start practicingGo further
You don't need these to start practicing. Open one when you want more.
Why it works
The reasoning that makes it always right
The function's promise, for any list, is: return the list sorted, and the number of inversions in it. For 0 or 1 items there are no pairs, so { sorted: items, count: 0 } keeps it. For longer lists, assume the two recursive calls keep it for the halves, which are shorter.
Every inversion of the whole list is inside the left half, inside the right half, or a cross pair, and no pair is more than one kind. The recursive counts cover the first two kinds exactly. Starting count at left.count + right.count adds them.
For cross pairs, think of each right item r. Its cross pairs are the left items bigger than r. In the merge, r is taken at the moment the front left item is bigger than it. Because left.sorted is sorted, all items from i to the end are bigger, and all items before i were taken earlier because they were <= r. So left.sorted.length - i is exactly r's number of cross pairs. Each right item is taken once, so each cross pair is counted once. Right items taken by the final push have i at the end of left, so they have zero cross pairs, and nothing is added.
Sorting the halves changes positions inside each half, but a cross pair only needs "left half, bigger" and "right half, smaller", which sorting doesn't change. So the counts are for the original list, and the merged list is sorted, keeping the promise.
Going deeper
3 more ideas
Why every inversion is counted exactly once
Any inversion (i, j) has both positions in the left half, both in the right half, or i in the left and j in the right. The first two kinds are counted by the recursive calls. A cross pair is counted at the moment its right item is taken during the merge: its left item is still waiting, because it is bigger. Taking each right item happens once, so each cross pair is counted once.
Inversions and adjacent swaps
Swapping two neighbors that are out of order fixes exactly one inversion. So the smallest number of adjacent swaps that sorts a list equals its inversion count, and it is also how many swaps bubble sort makes and how many shifts insertion sort makes.
How long it takes
It is merge sort with one extra addition per step, so it keeps merge sort's O(n log n) time and O(n) space. A list of 100,000 items has up to about 5 billion inversions, still well within JavaScript's safe integer range.
Work it by hand
Every step in a table, with why
Count the inversions in 6 numbers with two 3s. The small merges are shown in one row each, then the final merge step by step.
items = [6, 3, 8, 3, 1, 7]
| Step | Step | left.sorted | right.sorted | Added | count | What happens | Why |
|---|---|---|---|---|---|---|---|
| 1 | merge | [3] | [8] | 0 | 0 | 3 <= 8: no inversion | [3, 8] came from splitting [6, 3, 8] into [6] and [3, 8]. It is already in order. |
| 2 | merge | [6] | [3, 8] | 1 | 1 | 3 beats 6: +1 | One left item, 6, is waiting when 3 is taken. That is the pair (6, 3). |
| 3 | merge | [1] | [7] | 0 | 0 | 1 <= 7: no inversion | The right half [3, 1, 7] splits into [3] and [1, 7]. |
| 4 | merge | [3] | [1, 7] | 1 | 1 | 1 beats 3: +1 | The pair (3, 1), from positions 3 and 4 of the input. |
| 5 | final, i = 0, j = 0 | [3, 6, 8] | [1, 3, 7] | 3 | 5 | 1 beats all three: +3 | count starts at 1 + 1 = 2, from the halves. 1 is smaller than 3, 6, and 8, which were all before it. |
| 6 | i = 0, j = 1 | [3, 6, 8] | [1, 3, 7] | 0 | 5 | Tie 3 <= 3: take left | Equal items are not an inversion. The <= takes the left 3 without adding anything. |
| 7 | i = 1, j = 1 | [3, 6, 8] | [1, 3, 7] | 2 | 7 | Right 3 beats 6, 8: +2 | left.sorted.length - i is 3 - 1 = 2: the pairs (6, 3) and (8, 3). |
| 8 | i = 1, j = 2 | [3, 6, 8] | [1, 3, 7] | 0 | 7 | 6 <= 7: take 6 | Taking from the left never adds anything. |
| 9 | i = 2, j = 2 | [3, 6, 8] | [1, 3, 7] | 1 | 8 | 7 beats 8: +1 | Only 8 is still waiting: the pair (8, 7). |
| 10 | leftovers | [3, 6, 8] | [1, 3, 7] | 0 | 8 | Push the rest | right is used up. 8 is pushed with no addition: leftover left items have no right items after them. |
It returns count: 8, with sorted: [1, 3, 3, 6, 7, 8]. Checking all 15 pairs by hand confirms 8 inversions: 1 inside each half and 6 across the halves.
Compared with other ways
When to pick something else
| Approach | Time | Extra memory | Choose it when |
|---|---|---|---|
| Counting inversions | O(n log n) | O(n) | Large lists, or when you also want the sorted result. It is the standard answer. |
| Check every pair | O(n²) | O(1) | Lists of a few hundred items, or to check the fast version in tests. |
| Fenwick tree | O(n log n) | O(n) | You need per-item counts, or the values arrive one at a time from the right. |
| Bubble sort swap count | O(n²) | O(1) | Only for teaching: it gives the same number, one swap per inversion, but slowly. |
Extra memory: O(n): the slices and the sorted arrays at each level. The recursion is only about log₂ n calls deep.
How the steps grow
- Counting inversions, Fenwick tree
O(n log n) - Check every pair, Bubble sort swap count
O(n²)
| Approach | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| Counting inversions | 33 | 9,966 | 20 million |
| Check every pair | 100 | 1 million | 1 trillion |
| Fenwick tree | 33 | 9,966 | 20 million |
| Bubble sort swap count | 100 | 1 million | 1 trillion |
Inputs that need care
5 tricky inputs
- An empty list or one item
- The base case returns
count: 0. There are no pairs to count. - All equal:
[5, 5, 5, 5] - Every merge comparison is a tie, and
<=takes from the left, so nothing is added. The answer is0, which is right: equal items are not inversions. - Reversed:
[4, 3, 2, 1] - Every pair is an inversion, so the answer is
4 × 3 / 2 = 6. Each merge takes every right item first and adds the whole remaining left side. - A huge reversed list of 1,000,000 items
- The count is about 500 billion, still far below
Number.MAX_SAFE_INTEGER(about 9 quadrillion), so plain numbers are exact. Languages with 32-bit integers need 64-bit counters here. - You need the original array afterwards
- The code only reads
itemsthroughslice, so the input is not changed. The sorted copy comes back insorted.
Variations and follow-ups
Twists interviewers add
Count, for each item, the smaller items after it
Instead of one total, record a count per original index. Sort pairs of [value, index], and when a left item is taken, add the number of right items already taken to that item's count. It is the same merge, with the addition moved to the left side.
Fenwick tree counting
Walk the list from right to left, and for each value ask a Fenwick tree how many smaller values have been seen, then add the value to the tree. With values compressed to ranks, this is also O(n log n), and it answers "how many smaller after me?" directly.
Distance between two rankings
To measure how differently two people ranked the same 10 movies, rewrite the second ranking in the positions of the first, and count its inversions. That number, called the Kendall tau distance, is how many pairs the two rankings disagree on.
Pairs with a scaled condition
Counting pairs with items[i] > 2 × items[j] uses the same split, but the count must be taken in a separate pass over the sorted halves before merging, with its own pointer. The merge order follows >, not > 2 ×.
In an interview
Spot it, explain it, answer follow-ups
- Spot it from "how many pairs
i < jwitha[i] > a[j]", "how far from sorted", "minimum adjacent swaps to sort", or "how many people overtook each other". All of them are inversion counts. - Explain the three kinds of pairs first (left, right, cross), then the key line: when the right item wins, every remaining left item is bigger and earlier, so add
left.sorted.length - i. - Test by hand with a reversed list (the answer must be
n × (n - 1) / 2), a list with equal items (they must not count), and a sorted list (the answer is0). Compare against the double loop on small random lists. - The usual follow-up is "what if you need the count for each element?". Track original indexes through the merge, or use a Fenwick tree over value ranks.
Where frontend code uses it
The same idea in real UI code
- Scoring how close a user's drag-and-drop ordering is to the correct order, as in a sorting quiz: the inversion count is the number of pairs they got backwards.
- Comparing two rankings, such as yesterday's and today's trending list, by counting the pairs whose order changed.
- Knowing the minimum number of neighbor swaps needed to reach a target order, for example to plan a reorder animation that moves items one slot at a time.