Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Merge Sort and Counting Inversions

Editorial

The count everyone writes first

Inversion Count in Array asks how many pairs i < j have a[i] > a[j]: how far the array is from sorted. Arrays go up to 100,000 values. The first thing everyone writes checks every pair, here on 100,000 values in reverse order, where every pair counts:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 100000;
    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = n - i;      // reversed: every pair is out of order
    auto start = chrono::steady_clock::now();
    long long count = 0;
    for (int i = 0; i < n; i++)                     // every pair, the loop everyone writes first
        for (int j = i + 1; j < n; j++)
            if (a[i] > a[j]) count++;
    double s = chrono::duration<double>(chrono::steady_clock::now() - start).count();
    printf("%d: %lld inversions in %.2fs\n", n, count, s);
}

// 100000: 4999950000 inversions in 5.25s
import time

n = 10000                             # 100,000 would take about 100 times longer
a = list(range(n, 0, -1))             # reversed: every pair is out of order
start = time.perf_counter()
count = 0
for i in range(n):                    # every pair, the loop everyone writes first
    for j in range(i + 1, n):
        if a[i] > a[j]:
            count += 1
print(f"{n}: {count} inversions in {time.perf_counter() - start:.2f}s")

# 10000: 49995000 inversions in 10.68s
public class Main {
    public static void main(String[] args) {
        int n = 100000;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = n - i;  // reversed: every pair is out of order
        long start = System.nanoTime();
        int count = 0;
        for (int i = 0; i < n; i++)                 // every pair, the loop everyone writes first
            for (int j = i + 1; j < n; j++)
                if (a[i] > a[j]) count++;
        System.out.printf("%d: %d inversions in %.2fs%n", n, count, (System.nanoTime() - start) / 1e9);
    }
}

// 100000: 704982704 inversions in 1.76s
const n = 100000;
const a = Array.from({ length: n }, (_, i) => n - i);   // reversed: every pair is out of order
const start = process.hrtime.bigint();
let count = 0;
for (let i = 0; i < n; i++)                // every pair, the loop everyone writes first
    for (let j = i + 1; j < n; j++)
        if (a[i] > a[j]) count++;
const s = Number(process.hrtime.bigint() - start) / 1e9;
console.log(`${n}: ${count} inversions in ${s.toFixed(2)}s`);

// 100000: 4999950000 inversions in 22.44s

The answer is 4,999,950,000. C++ took 5.25 s and JavaScript 22.44 s to find it. Java took 1.76 s and printed 704,982,704: its int count passed 2,147,483,647 and wrapped around. Python checked 10,000 values in 10.68 s; 100,000 is a hundred times the pairs, about 18 minutes.

Merge sort counts the same pairs while it sorts, in O(n log n): below, the same 100,000 values take 3.3 ms in C++ and 0.45 s in Python. This lesson builds merge sort, then makes it count: inversions, then Reverse Pairs.

Three dashed panels. Split: four rows of tiles, 5 2 4 7 1 3 2 6, then 5 2 4 7 and 1 3 2 6, then 5 2, 4 7, 1 3 and 2 6, then the eight single values in orange. Merge, in green: 2 5, 4 7, 1 3 and 2 6, then 2 4 5 7 and 1 2 3 6, then 1 2 2 3 4 5 6 7. The cost: 8 values halve to 1 in 3 levels, log₂ 8 = 3; each merge level writes all 8 once, 3 × 8 = 24; n values, log₂ n levels: O(n log n). Focal line: split to single values, then merge sorted runs back up. Title: split, sort each half, merge.

Merge sort

Split the array in half, sort each half the same way, then merge the two sorted halves. A run of one value is already sorted, so the splitting stops there, and all the work is in the merge: two sorted runs, a pointer at the front of each, and the smaller front value taken each time until one run is used up. The rest of the other run follows as it is:

#include <bits/stdc++.h>
using namespace std;

uint32_t seed = 2463534242u;

int randomBelow(int bound) {                 // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed % bound;
}

vector<int> shuffled(int n) {                // 0 .. n-1 in a random order
    vector<int> nums(n);
    iota(nums.begin(), nums.end(), 0);
    for (int i = n - 1; i > 0; i--) swap(nums[i], nums[randomBelow(i + 1)]);
    return nums;
}

long long comparisons = 0;

void mergeRuns(vector<int>& a, int lo, int mid, int hi, vector<int>& tmp) {   // a[lo..mid), a[mid..hi) are sorted
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        comparisons++;
        if (a[i] <= a[j]) tmp[k++] = a[i++];   // on a tie take the left one: equal values keep their order
        else tmp[k++] = a[j++];
    }
    while (i < mid) tmp[k++] = a[i++];         // one run is used up: the rest of the other follows
    while (j < hi) tmp[k++] = a[j++];
    for (k = lo; k < hi; k++) a[k] = tmp[k];
}

void mergeSort(vector<int>& a, int lo, int hi, vector<int>& tmp) {   // sorts a[lo..hi)
    if (hi - lo <= 1) return;
    int mid = (lo + hi) / 2;
    mergeSort(a, lo, mid, tmp);
    mergeSort(a, mid, hi, tmp);
    mergeRuns(a, lo, mid, hi, tmp);
}

int main() {
    vector<int> a = {5, 2, 4, 7, 1, 3, 2, 6}, tmp(a.size());
    mergeSort(a, 0, a.size(), tmp);
    for (size_t k = 0; k < a.size(); k++) printf(k ? " %d" : "%d", a[k]);
    printf("\n");
    vector<int> b = shuffled(1000), tmp2(1000);
    comparisons = 0;
    mergeSort(b, 0, b.size(), tmp2);
    printf("1,000 shuffled values: %lld comparisons\n", comparisons);
}

// 1 2 2 3 4 5 6 7
// 1,000 shuffled values: 8707 comparisons
seed = 2463534242


def random_below(bound):              # xorshift: the same numbers in every language
    global seed
    seed ^= (seed << 13) & 0xFFFFFFFF
    seed ^= seed >> 17
    seed ^= (seed << 5) & 0xFFFFFFFF
    return seed % bound


def shuffled(n):                      # 0 .. n-1 in a random order
    nums = list(range(n))
    for i in range(n - 1, 0, -1):
        j = random_below(i + 1)
        nums[i], nums[j] = nums[j], nums[i]
    return nums

comparisons = 0


def merge(left, right):               # two sorted runs into one, taking the smaller front each time
    global comparisons
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        comparisons += 1
        if left[i] <= right[j]:       # on a tie take the left one: equal values keep their order
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    return out + left[i:] + right[j:]   # one run is used up: the rest of the other follows


def merge_sort(a):                    # split, sort each half, merge the two sorted halves
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))


print(*merge_sort([5, 2, 4, 7, 1, 3, 2, 6]))
comparisons = 0
merge_sort(shuffled(1000))
print(f"1,000 shuffled values: {comparisons} comparisons")

# 1 2 2 3 4 5 6 7
# 1,000 shuffled values: 8707 comparisons
import java.util.*;

public class Main {
    static int seed = (int) 2463534242L;

    static int randomBelow(int bound) {          // xorshift: the same numbers in every language
        seed ^= seed << 13;
        seed ^= seed >>> 17;
        seed ^= seed << 5;
        return Integer.remainderUnsigned(seed, bound);
    }

    static int[] shuffled(int n) {               // 0 .. n-1 in a random order
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = i;
        for (int i = n - 1; i > 0; i--) {
            int j = randomBelow(i + 1), t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
        return nums;
    }

    static long comparisons = 0;

    static void mergeRuns(int[] a, int lo, int mid, int hi, int[] tmp) {   // a[lo..mid), a[mid..hi) are sorted
        int i = lo, j = mid, k = lo;
        while (i < mid && j < hi) {
            comparisons++;
            if (a[i] <= a[j]) tmp[k++] = a[i++];   // on a tie take the left one: equal values keep their order
            else tmp[k++] = a[j++];
        }
        while (i < mid) tmp[k++] = a[i++];         // one run is used up: the rest of the other follows
        while (j < hi) tmp[k++] = a[j++];
        for (k = lo; k < hi; k++) a[k] = tmp[k];
    }

    static void mergeSort(int[] a, int lo, int hi, int[] tmp) {   // sorts a[lo..hi)
        if (hi - lo <= 1) return;
        int mid = (lo + hi) / 2;
        mergeSort(a, lo, mid, tmp);
        mergeSort(a, mid, hi, tmp);
        mergeRuns(a, lo, mid, hi, tmp);
    }

    public static void main(String[] args) {
        int[] a = {5, 2, 4, 7, 1, 3, 2, 6};
        mergeSort(a, 0, a.length, new int[a.length]);
        StringJoiner line = new StringJoiner(" ");
        for (int v : a) line.add(String.valueOf(v));
        System.out.println(line);
        int[] b = shuffled(1000);
        comparisons = 0;
        mergeSort(b, 0, b.length, new int[b.length]);
        System.out.println("1,000 shuffled values: " + comparisons + " comparisons");
    }
}

// 1 2 2 3 4 5 6 7
// 1,000 shuffled values: 8707 comparisons
let seed = 2463534242;

function randomBelow(bound) {                // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >>> 17;
    seed ^= seed << 5;
    return (seed >>> 0) % bound;
}

function shuffled(n) {                       // 0 .. n-1 in a random order
    const nums = Array.from({ length: n }, (_, i) => i);
    for (let i = n - 1; i > 0; i--) {
        const j = randomBelow(i + 1);
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    return nums;
}

let comparisons = 0;

function mergeRuns(a, lo, mid, hi, tmp) {  // a[lo..mid) and a[mid..hi) are sorted
    let i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        comparisons++;
        if (a[i] <= a[j]) tmp[k++] = a[i++];   // on a tie take the left one: equal values keep their order
        else tmp[k++] = a[j++];
    }
    while (i < mid) tmp[k++] = a[i++];         // one run is used up: the rest of the other follows
    while (j < hi) tmp[k++] = a[j++];
    for (k = lo; k < hi; k++) a[k] = tmp[k];
}

function mergeSort(a, lo, hi, tmp) {       // sorts a[lo..hi)
    if (hi - lo <= 1) return;
    const mid = Math.floor((lo + hi) / 2);
    mergeSort(a, lo, mid, tmp);
    mergeSort(a, mid, hi, tmp);
    mergeRuns(a, lo, mid, hi, tmp);
}

const a = [5, 2, 4, 7, 1, 3, 2, 6];
mergeSort(a, 0, a.length, new Array(a.length));
console.log(a.join(" "));
const b = shuffled(1000);
comparisons = 0;
mergeSort(b, 0, b.length, new Array(b.length));
console.log(`1,000 shuffled values: ${comparisons} comparisons`);

// 1 2 2 3 4 5 6 7
// 1,000 shuffled values: 8707 comparisons

On the 1,000 shuffled values of Introduction to Sorting, merge sort made 8,707 comparisons, where insertion sort made 249,457.

Every level of splitting halves the runs, so there are about log₂ n levels, and the merges on one level touch every value once: O(n log n) on every input, sorted or not. Recurrence Relations and the Master Theorem writes this as T(n) = 2T(n/2) + n and sums it level by level. Two more properties come from the merge itself:

  • Stable. On a tie the left value goes first, so equal values keep their order. That <= matters.
  • O(n) extra space. The merged run needs a buffer as long as the input; merge sort on an array isn't in place.

Counting while merging

Back to the inversions. When the merge takes a value from the right run, that value is smaller than every value still waiting in the left run, and each of those sat before it in the array: each is one inversion. So the merge adds the number of values left in the left run, and taking from the left adds nothing. Inversions inside each half were counted by the calls that sorted it:

Two dashed panels. Left, taking the 3: the left run 2, 5, 8 in orange with 2 pale (taken) and 5 and 8 ringed in red; the right run 1, 3, 9 in blue with 1 pale and 3 ringed in orange; the merged row 1, 2, 3 in green and three empty slots, an arrow from the 3 down into it; 3 < 5: take the 3. 5 and 8 still wait, and both sat before it: +2 inversions. Right, every pick: take 1, right: +3; take 2, left: +0; take 3, right: +2; take 5, left: +0; take 8, left: +0; then 9 follows; total: 5; every pair checked: 5. Focal line: a right pick adds every value still waiting on the left. Title: a right pick jumps the left run.
#include <bits/stdc++.h>
using namespace std;

long long sortCount(vector<int>& a, int lo, int hi, vector<int>& tmp) {   // sorts a[lo..hi), counts its inversions
    if (hi - lo <= 1) return 0;
    int mid = (lo + hi) / 2;
    long long count = sortCount(a, lo, mid, tmp) + sortCount(a, mid, hi, tmp);
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            count += mid - i;                  // a[j] is smaller than every value left in the left run
            tmp[k++] = a[j++];
        }
    }
    while (i < mid) tmp[k++] = a[i++];
    while (j < hi) tmp[k++] = a[j++];
    for (k = lo; k < hi; k++) a[k] = tmp[k];
    return count;
}

long long inversions(vector<int> a) {
    vector<int> tmp(a.size());
    return sortCount(a, 0, a.size(), tmp);
}

int main() {
    printf("%lld %lld %lld\n", inversions({8, 4, 2, 1}), inversions({2, 4, 1, 3, 5}), inversions({1, 1, 1}));
    vector<int> big(100000);
    for (int i = 0; i < 100000; i++) big[i] = 100000 - i;
    auto start = chrono::steady_clock::now();
    long long count = inversions(big);
    double s = chrono::duration<double>(chrono::steady_clock::now() - start).count();
    printf("100000 reversed: %lld inversions in %.4fs\n", count, s);
}

// 6 3 0
// 100000 reversed: 4999950000 inversions in 0.0033s
import time


def sort_count(a):                    # returns a sorted, and how many pairs i < j had a[i] > a[j]
    if len(a) <= 1:
        return a, 0
    mid = len(a) // 2
    left, x = sort_count(a[:mid])
    right, y = sort_count(a[mid:])
    out, i, j, count = [], 0, 0, x + y
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            count += len(left) - i    # right[j] is smaller than every value left in the left run
            out.append(right[j])
            j += 1
    return out + left[i:] + right[j:], count


print(*(sort_count(a)[1] for a in ([8, 4, 2, 1], [2, 4, 1, 3, 5], [1, 1, 1])))
big = list(range(100000, 0, -1))
start = time.perf_counter()
count = sort_count(big)[1]
print(f"100000 reversed: {count} inversions in {time.perf_counter() - start:.4f}s")

# 6 3 0
# 100000 reversed: 4999950000 inversions in 0.4528s
public class Main {
    static long sortCount(int[] a, int lo, int hi, int[] tmp) {   // sorts a[lo..hi), counts its inversions
        if (hi - lo <= 1) return 0;
        int mid = (lo + hi) / 2;
        long count = sortCount(a, lo, mid, tmp) + sortCount(a, mid, hi, tmp);
        int i = lo, j = mid, k = lo;
        while (i < mid && j < hi) {
            if (a[i] <= a[j]) tmp[k++] = a[i++];
            else {
                count += mid - i;              // a[j] is smaller than every value left in the left run
                tmp[k++] = a[j++];
            }
        }
        while (i < mid) tmp[k++] = a[i++];
        while (j < hi) tmp[k++] = a[j++];
        for (k = lo; k < hi; k++) a[k] = tmp[k];
        return count;
    }

    static long inversions(int[] a) {
        int[] copy = a.clone();
        return sortCount(copy, 0, copy.length, new int[copy.length]);
    }

    public static void main(String[] args) {
        System.out.println(inversions(new int[]{8, 4, 2, 1}) + " " + inversions(new int[]{2, 4, 1, 3, 5}) + " "
            + inversions(new int[]{1, 1, 1}));
        int[] big = new int[100000];
        for (int i = 0; i < big.length; i++) big[i] = big.length - i;
        long start = System.nanoTime();
        long count = inversions(big);
        System.out.printf("100000 reversed: %d inversions in %.4fs%n", count, (System.nanoTime() - start) / 1e9);
    }
}

// 6 3 0
// 100000 reversed: 4999950000 inversions in 0.0321s
function sortCount(a, lo, hi, tmp) {     // sorts a[lo..hi), counts its inversions
    if (hi - lo <= 1) return 0;
    const mid = Math.floor((lo + hi) / 2);
    let count = sortCount(a, lo, mid, tmp) + sortCount(a, mid, hi, tmp);
    let i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            count += mid - i;                  // a[j] is smaller than every value left in the left run
            tmp[k++] = a[j++];
        }
    }
    while (i < mid) tmp[k++] = a[i++];
    while (j < hi) tmp[k++] = a[j++];
    for (k = lo; k < hi; k++) a[k] = tmp[k];
    return count;
}

const inversions = (a) => sortCount(a.slice(), 0, a.length, new Array(a.length));

console.log([[8, 4, 2, 1], [2, 4, 1, 3, 5], [1, 1, 1]].map(inversions).join(" "));
const big = Array.from({ length: 100000 }, (_, i) => 100000 - i);
const start = process.hrtime.bigint();
const count = inversions(big);
console.log(`100000 reversed: ${count} inversions in ${(Number(process.hrtime.bigint() - start) / 1e9).toFixed(4)}s`);

// 6 3 0
// 100000 reversed: 4999950000 inversions in 0.0406s

[8, 4, 2, 1] has 6 inversions, every pair, and [2, 4, 1, 3, 5] has 3: (2, 1), (4, 1) and (4, 3). The 100,000 reversed values took 3.3 ms in C++, 32.1 ms in Java, 40.6 ms in JavaScript and 0.45 s in Python, and every count is 4,999,950,000: a 64-bit integer, since n(n − 1)/2 passes 2³¹ − 1 once n is over 65,536.

Merge Two Runs. Merge two sorted runs yourself: pick the run whose front comes next. In count mode, every pick from the right run adds the values it jumps; ties show why the left one goes first.

Merge Two Runs: take the smaller front, and count the values each right pick jumps

Reverse Pairs: count before you merge

Reverse Pairs counts pairs i < j with nums[i] > 2 × nums[j]. The merge can't count these on its own: the order it takes values in is by plain comparison, not by twice the value. But just before merging, both halves are sorted, and that's enough. For each value in the left half, move a pointer through the right half while the value is more than twice the right one; everything the pointer passed pairs with it. The next left value is bigger, so the pointer never moves back, and the count costs O(n) per merge:

Two dashed panels. Left, two sorted halves: the left half 3, 5, 8 in orange; the right half 1, 2, 3 in blue; under it, × 2: 2, 4, 6 in purple; a track with an arrow, j only moves forward, and red marks where j stops for 3 (after the first), for 5 (after the second) and for 8 (after the third). Right, for each left value: 3 > 2, not 4: +1; 5 > 2, 4, not 6: +2; 8 > 2, 4, 6: +3; 1 + 2 + 3 = 6 pairs; every pair checked: 6; then merge the halves as usual. Focal line: both halves sorted: the pointer never moves back. Title: count before you merge.
#include <bits/stdc++.h>
using namespace std;

long long sortCount(vector<int>& a, int lo, int hi, vector<int>& tmp) {   // pairs i < j with a[i] > 2 * a[j]
    if (hi - lo <= 1) return 0;
    int mid = (lo + hi) / 2;
    long long count = sortCount(a, lo, mid, tmp) + sortCount(a, mid, hi, tmp);
    int j = mid;
    for (int i = lo; i < mid; i++) {           // both halves sorted: j only moves forward
        while (j < hi && a[i] > 2LL * a[j]) j++;   // 2LL: twice an int can pass the largest int
        count += j - mid;
    }
    merge(a.begin() + lo, a.begin() + mid, a.begin() + mid, a.begin() + hi, tmp.begin() + lo);
    copy(tmp.begin() + lo, tmp.begin() + hi, a.begin() + lo);
    return count;
}

long long reversePairs(vector<int> a) {
    vector<int> tmp(a.size());
    return sortCount(a, 0, a.size(), tmp);
}

int main() {
    vector<vector<int>> tests = {{1, 3, 2, 3, 1}, {2, 4, 3, 5, 1}, {2147483647, 1073741824}, {-5, -5}};
    for (size_t t = 0; t < tests.size(); t++) printf(t ? " %lld" : "%lld", reversePairs(tests[t]));
    printf("\n");
}

// 2 3 0 1
def reverse_pairs(nums):              # pairs i < j with nums[i] > 2 * nums[j]
    def sort_count(a):
        if len(a) <= 1:
            return a, 0
        mid = len(a) // 2
        left, x = sort_count(a[:mid])
        right, y = sort_count(a[mid:])
        count, j = x + y, 0
        for v in left:                # both halves sorted: j only moves forward
            while j < len(right) and v > 2 * right[j]:
                j += 1
            count += j
        merged, i, k = [], 0, 0
        while i < len(left) and k < len(right):
            if left[i] <= right[k]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[k])
                k += 1
        return merged + left[i:] + right[k:], count
    return sort_count(nums)[1]


print(*(reverse_pairs(t) for t in ([1, 3, 2, 3, 1], [2, 4, 3, 5, 1], [2147483647, 1073741824], [-5, -5])))

# 2 3 0 1
import java.util.*;

public class Main {
    static long sortCount(int[] a, int lo, int hi, int[] tmp) {   // pairs i < j with a[i] > 2 * a[j]
        if (hi - lo <= 1) return 0;
        int mid = (lo + hi) / 2;
        long count = sortCount(a, lo, mid, tmp) + sortCount(a, mid, hi, tmp);
        int j = mid;
        for (int i = lo; i < mid; i++) {       // both halves sorted: j only moves forward
            while (j < hi && a[i] > 2L * a[j]) j++;   // 2L: twice an int can pass the largest int
            count += j - mid;
        }
        int i = lo, k = lo;
        j = mid;
        while (i < mid && j < hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
        while (i < mid) tmp[k++] = a[i++];
        while (j < hi) tmp[k++] = a[j++];
        for (k = lo; k < hi; k++) a[k] = tmp[k];
        return count;
    }

    static long reversePairs(int[] a) {
        int[] copy = a.clone();
        return sortCount(copy, 0, copy.length, new int[copy.length]);
    }

    public static void main(String[] args) {
        int[][] tests = {{1, 3, 2, 3, 1}, {2, 4, 3, 5, 1}, {2147483647, 1073741824}, {-5, -5}};
        StringJoiner line = new StringJoiner(" ");
        for (int[] t : tests) line.add(String.valueOf(reversePairs(t)));
        System.out.println(line);
    }
}

// 2 3 0 1
function sortCount(a, lo, hi, tmp) {     // pairs i < j with a[i] > 2 * a[j]
    if (hi - lo <= 1) return 0;
    const mid = Math.floor((lo + hi) / 2);
    let count = sortCount(a, lo, mid, tmp) + sortCount(a, mid, hi, tmp);
    let j = mid;
    for (let i = lo; i < mid; i++) {           // both halves sorted: j only moves forward
        while (j < hi && a[i] > 2 * a[j]) j++;
        count += j - mid;
    }
    let i = lo, k = lo;
    j = mid;
    while (i < mid && j < hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    while (i < mid) tmp[k++] = a[i++];
    while (j < hi) tmp[k++] = a[j++];
    for (k = lo; k < hi; k++) a[k] = tmp[k];
    return count;
}

const reversePairs = (a) => sortCount(a.slice(), 0, a.length, new Array(a.length));

console.log([[1, 3, 2, 3, 1], [2, 4, 3, 5, 1], [2147483647, 1073741824], [-5, -5]].map(reversePairs).join(" "));

// 2 3 0 1

The problem's two examples give 2 and 3. [2147483647, 1073741824] gives 0: twice 1,073,741,824 is 2,147,483,648, one more than the first value, and computing it needs 64 bits (2LL in C++, 2L in Java). [−5, −5] gives 1, since twice a negative number is smaller.

Without recursion, on lists and on disk

Bottom-up merge sort skips the splitting: merge runs of 1 into runs of 2, then 2s into 4s, and so on, with a loop instead of calls:

#include <bits/stdc++.h>
using namespace std;

void bottomUp(vector<int>& a) {               // merge runs of 1, then 2, then 4, ... with no recursion
    int n = a.size();
    vector<int> tmp(n);
    for (int width = 1; width < n; width *= 2) {
        for (int lo = 0; lo < n; lo += 2 * width) {
            int mid = min(lo + width, n), hi = min(lo + 2 * width, n);
            merge(a.begin() + lo, a.begin() + mid, a.begin() + mid, a.begin() + hi, tmp.begin() + lo);
        }
        a = tmp;
        printf("runs of %d:", 2 * width);
        for (int v : a) printf(" %d", v);
        printf("\n");
    }
}

int main() {
    vector<int> a = {5, 2, 4, 7, 1, 3, 2, 6};
    bottomUp(a);
}

// runs of 2: 2 5 4 7 1 3 2 6
// runs of 4: 2 4 5 7 1 2 3 6
// runs of 8: 1 2 2 3 4 5 6 7
def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    return out + left[i:] + right[j:]


def bottom_up(a):                     # merge runs of 1, then 2, then 4, ... with no recursion
    n, width = len(a), 1
    while width < n:
        for lo in range(0, n, 2 * width):
            mid, hi = min(lo + width, n), min(lo + 2 * width, n)
            a[lo:hi] = merge(a[lo:mid], a[mid:hi])
        print(f"runs of {2 * width}:", *a)
        width *= 2


bottom_up([5, 2, 4, 7, 1, 3, 2, 6])

# runs of 2: 2 5 4 7 1 3 2 6
# runs of 4: 2 4 5 7 1 2 3 6
# runs of 8: 1 2 2 3 4 5 6 7
public class Main {
    static void bottomUp(int[] a) {        // merge runs of 1, then 2, then 4, ... with no recursion
        int n = a.length;
        int[] tmp = new int[n];
        for (int width = 1; width < n; width *= 2) {
            for (int lo = 0; lo < n; lo += 2 * width) {
                int mid = Math.min(lo + width, n), hi = Math.min(lo + 2 * width, n);
                int i = lo, j = mid, k = lo;
                while (i < mid && j < hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
                while (i < mid) tmp[k++] = a[i++];
                while (j < hi) tmp[k++] = a[j++];
            }
            System.arraycopy(tmp, 0, a, 0, n);
            StringBuilder line = new StringBuilder("runs of " + 2 * width + ":");
            for (int v : a) line.append(" ").append(v);
            System.out.println(line);
        }
    }

    public static void main(String[] args) {
        bottomUp(new int[]{5, 2, 4, 7, 1, 3, 2, 6});
    }
}

// runs of 2: 2 5 4 7 1 3 2 6
// runs of 4: 2 4 5 7 1 2 3 6
// runs of 8: 1 2 2 3 4 5 6 7
function bottomUp(a) {                   // merge runs of 1, then 2, then 4, ... with no recursion
    const n = a.length, tmp = new Array(n);
    for (let width = 1; width < n; width *= 2) {
        for (let lo = 0; lo < n; lo += 2 * width) {
            const mid = Math.min(lo + width, n), hi = Math.min(lo + 2 * width, n);
            let i = lo, j = mid, k = lo;
            while (i < mid && j < hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
            while (i < mid) tmp[k++] = a[i++];
            while (j < hi) tmp[k++] = a[j++];
        }
        for (let k = 0; k < n; k++) a[k] = tmp[k];
        console.log(`runs of ${2 * width}: ${a.join(" ")}`);
    }
}

bottomUp([5, 2, 4, 7, 1, 3, 2, 6]);

// runs of 2: 2 5 4 7 1 3 2 6
// runs of 4: 2 4 5 7 1 2 3 6
// runs of 8: 1 2 2 3 4 5 6 7

Same merges, same O(n log n), no call stack.

Linked lists suit merge sort best: finding the middle and relinking cost no extra array, and the merge only rewires nodes (Sort List, in Linked List). Runs too big for memory are sorted the same way at a larger scale: sort chunks that fit, write them out, then merge the sorted chunks k at a time with a heap (Merging and Scheduling with a Heap). That's external sorting.

Spotting it

The clue is a count of pairs i < j by their values: inversions, "how many smaller numbers after this one", pairs with nums[i] > k × nums[j], or how many swaps of neighbours would sort the array (exactly the inversions). Merge sort counts them while the halves are sorted. Near misses:

  • Pairs by a sum, where positions don't matter: sort and use two pointers (Two Pointers).
  • Counts per element under changing values: a Fenwick tree does it (Advanced Topics).
  • Sorting a linked list: merge sort, with the middle found by fast and slow pointers.

Mistakes that cost an interview

Counting in an int. n(n − 1)/2 inversions don't fit 32 bits. The merge count with an int in Java printed 704,982,704 for the 100,000 reversed values, the same wrong number as the pair loop:

public class Main {
    static int sortCount(int[] a, int lo, int hi, int[] tmp) {    // the count in an int
        if (hi - lo <= 1) return 0;
        int mid = (lo + hi) / 2;
        int count = sortCount(a, lo, mid, tmp) + sortCount(a, mid, hi, tmp);
        int i = lo, j = mid, k = lo;
        while (i < mid && j < hi) {
            if (a[i] <= a[j]) tmp[k++] = a[i++];
            else { count += mid - i; tmp[k++] = a[j++]; }
        }
        while (i < mid) tmp[k++] = a[i++];
        while (j < hi) tmp[k++] = a[j++];
        for (k = lo; k < hi; k++) a[k] = tmp[k];
        return count;
    }

    public static void main(String[] args) {
        int[] big = new int[100000];
        for (int i = 0; i < big.length; i++) big[i] = big.length - i;
        System.out.println(sortCount(big, 0, big.length, new int[big.length]));
    }
}

// 704982704

Taking the right value on a tie. Then an equal value counts as an inversion, and the sort isn't stable any more:

def count(a, take_left_on_tie):
    if len(a) <= 1:
        return a, 0
    mid = len(a) // 2
    left, x = count(a[:mid], take_left_on_tie)
    right, y = count(a[mid:], take_left_on_tie)
    out, i, j, n = [], 0, 0, x + y
    while i < len(left) and j < len(right):
        takes_left = left[i] <= right[j] if take_left_on_tie else left[i] < right[j]
        if takes_left:
            out.append(left[i])
            i += 1
        else:
            n += len(left) - i
            out.append(right[j])
            j += 1
    return out + left[i:] + right[j:], n


for a in ([1, 1], [2, 2, 1]):
    print(a, "with <=:", count(a, True)[1], "with <:", count(a, False)[1])

# [1, 1] with <=: 0 with <: 1
# [2, 2, 1] with <=: 2 with <: 3

Doubling in 32 bits. In Reverse Pairs, 2 * nums[j] overflows for nums[j] above 1,073,741,823:

public class Main {
    public static void main(String[] args) {
        int a = 2147483647, b = 1073741824;     // a pair from Reverse Pairs' range
        System.out.println("a > 2 * b: " + (a > 2 * b) + ", a > 2L * b: " + (a > 2L * b));
    }
}

// a > 2 * b: true, a > 2L * b: false

The 32-bit product wrapped to a negative number, so the pair counted. Multiply in 64 bits.

Check yourself

Quiz

1 / 6

Multiple choice

How many inversions does [3, 1, 2] have?

Practice

In this section, easy to hard:

  • Merge Sort: split, sort each half, merge with <=.
  • Inversion Count in Array: count jumps while merging, in 64 bits.
  • Reverse Pairs: count with a forward-only pointer before each merge.

Next: Quick Sort and Partitioning, the sort that puts one value in place first and splits around it.