⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#315) before relying on it.

Count Inversions

An interactive visualization of modified merge sort for counting inversions. Watch how inversions are detected during the merge step when an element from the right subarray is placed before remaining elements in the left subarray.

Divide and Conquer LeetCode 315 ↗ Hard

The Problem

Given an array of integers arr, count the number of inversion pairs (i, j) where i < j but arr[i] > arr[j].

An inversion indicates two elements that are "out of order" relative to a sorted arrangement. The total inversion count measures how far the array is from being sorted.

A brute-force approach checks all pairs in O(n²), but a modified merge sort solves this in O(n log n) by counting inversions during the merge step.

Interactive Visualization

Array (comma-separated)

Preset

Speed:

Merge Sort — Inversion Counting

Total Inversions

Code

fun countInversions(arr: List<Int>): Pair<List<Int>, Int> {    if (arr.size <= 1)        return Pair(arr, 0)    val mid = arr.size / 2    val (left, leftInv) = countInversions(arr.subList(0, mid))    val (right, rightInv) = countInversions(arr.subList(mid, arr.size))    val (merged, splitInv) = mergeCount(left, right)    return Pair(merged, leftInv + rightInv + splitInv)}fun mergeCount(left: List<Int>, right: List<Int>): Pair<List<Int>, Int> {    val result = mutableListOf<Int>()    var inversions = 0    var i = 0; var j = 0    while (i < left.size && j < right.size) {        if (left[i] <= right[j]) {            result.add(left[i])            i++        } else { // inversion found!            result.add(right[j])            inversions += left.size - i            j++    } }    result.addAll(left.subList(i, left.size) + right.subList(j, right.size))    return Pair(result, inversions)

def countInversions(arr):    if len(arr) <= 1:        return arr, 0    mid = len(arr) // 2    left, left_inv = countInversions(arr[:mid])    right, right_inv = countInversions(arr[mid:])    merged, split_inv = mergeCount(left, right)    return merged, left_inv + right_inv + split_invdef mergeCount(left, right):    result = []    inversions = 0    i = j = 0    while i < len(left) and j < len(right):        if left[i] <= right[j]:            result.append(left[i])            i += 1        else:  # inversion found!            result.append(right[j])            inversions += len(left) - i            j += 1    result.extend(left[i:])    result.extend(right[j:])    return result, inversions

Status

Press Step or Play to begin.

How It Works

Key Insight

During the merge step of merge sort, when we pick an element from the right subarray before all elements in the left subarray have been placed, each such pick means that element is smaller than all remaining elements in the left subarray. These are exactly the split inversions — we add len(left) - i to the inversion count (where i is the current index in the left subarray).

The Algorithm

Divide: Split the array into two halves recursively until each subarray has at most 1 element (0 inversions).
Conquer: Recursively count inversions in the left half (left_inv) and right half (right_inv).
Combine: Merge the two sorted halves while counting split inversions — pairs where one element is in the left half and the other in the right.
Counting inversions: When left[i] > right[j], all remaining elements in the left subarray (left[i..end]) form inversions with right[j].
Result: Total inversions = left_inv + right_inv + split_inv.

Complexity

Time O(n log n)

Space O(n)

Same as standard merge sort — we do O(n) work at each of O(log n) levels of recursion. The auxiliary space is O(n) for the temporary arrays used during merging.