SyntaxPilot
Courses/DSA and Coding Problems/Lesson 17

DSA and Coding Problems · Lesson 17 of 90 · 16 min

Merge sort and counting inversions

queued

These are the notes for DSA episode 17, the second episode of the sorting block. Episode 16 ended with a problem: on two lakh random numbers, bubble, selection and insertion sort all hit the time limit, because they are O(n²). Here we invent merge sort, a divide and conquer sort that is O(n log n) in every case, and then use it to solve a classic interview problem, counting inversions, by adding one line to the merge. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

Exam results day. The office has a pile of 40 jumbled answer sheets that must be sorted by roll number. One person alone is slow (that is what the simple sorts do). So the head clerk works like this:

In the exam office In merge sort
Split the pile in half, hand each half to a helper; they split again, and again Divide: split the array into two halves, recursively
A helper holding one sheet has nothing to do: it is already sorted Base case: a part of size 0 or 1 is sorted
A helper gets two sorted piles, compares the two top sheets, takes the smaller one, repeats Combine: merge two sorted halves

Splitting the work and then combining the results is called divide and conquer.

Problem statements

Problem 1, sorting. Sort an array of up to 2 × 10⁵ integers in non-decreasing order, fast: [5, 1, 4, 2, 8] → [1, 2, 4, 5, 8].

Problem 2, counting inversions. An inversion is a pair of indices i < j with a[i] > a[j] (a bigger value before a smaller one). Count them.

  • [5, 1, 4, 2, 8] → (5,1), (5,4), (5,2), (4,2) → 4
  • a sorted array → 0; a reversed array of length n → n(n - 1)/2 (every pair)
  • [3, 3, 1, 3] → 2 (each 3 before the 1; equal values are not inversions)
  • Constraints: n up to 2 × 10⁵, so the answer can be about 2 × 10¹⁰: it needs a long.

Real-life meaning: Asha and Ravi rank the same five movies. Write Ravi's scores in Asha's order. Each pair of movies they rank differently is an inversion, so the count measures how much their tastes disagree (this is the idea behind the Kendall tau distance used by ranking and recommendation systems). It is also exactly the number of swaps bubble sort makes (episode 16's homework answer: 4).

The merge: two sorted piles into one

Pointer i walks the left pile, j the right pile. Always take the smaller top; when one pile is empty, copy the rest of the other.

Step Left top Right top Take Merged so far
1 1 2 1 (left) [1]
2 4 2 2 (right) [1, 2]
3 4 8 4 (left) [1, 2, 4]
4 5 8 5 (left) [1, 2, 4, 5]
5 (empty) 8 copy leftovers [1, 2, 4, 5, 8]

Each step places one element, so merging n elements is O(n).

Merge sort

On [5, 1, 4, 2, 8]:

split:     [5, 1, 4]            [2, 8]
split:     [5, 1]    [4]        [2]  [8]
size 1:    [5] [1]   [4]        [2]  [8]      ← already sorted
merge:     [1, 5]    [4]        [2, 8]
merge:     [1, 4, 5]            [2, 8]
merge:     [1, 2, 4, 5, 8]

We use half-open ranges [lo, hi): lo is included, hi is not (like substring and most Java APIs). The part has hi - lo elements.

import java.util.*;

public class Main {
    static void mergeSort(int[] a) {
        sort(a, new int[a.length], 0, a.length);
    }
    static void sort(int[] a, int[] tmp, int lo, int hi) {
        if (hi - lo <= 1) return;
        int mid = (lo + hi) / 2;
        sort(a, tmp, lo, mid);
        sort(a, tmp, mid, hi);
        merge(a, tmp, lo, mid, hi);
    }
    static void merge(int[] a, int[] tmp, int lo, int mid, int hi) {
        int i = lo, j = mid, k = lo;
        while (i < mid && j < hi)
            if (a[i] <= a[j]) tmp[k++] = a[i++];
            else 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];
    }
    public static void main(String[] args) {
        int[] a = {5, 1, 4, 2, 8};
        mergeSort(a);
        System.out.println(Arrays.toString(a));
        int[] e = {};
        mergeSort(e);
        System.out.println(Arrays.toString(e));
        int[] d = {3, 3, 1, 3, 7};
        mergeSort(d);
        System.out.println(Arrays.toString(d));
    }
}

Output:

[1, 2, 4, 5, 8]
[]
[1, 3, 3, 3, 7]

Notes on the code:

  • a[i] <= a[j]: on a tie the left element goes first, so equal values keep their order: merge sort is stable.
  • One temporary array tmp is created once, in mergeSort, and shared by every merge (allocating a new array in every call also works, but is slower).
  • (lo + hi) / 2 is safe here; for ranges near 2³¹ write lo + (hi - lo) / 2 to avoid overflow.

The base-case bug: StackOverflowError

        if (lo == hi) return;      // wrong for a half-open range
Exception in thread "main" java.lang.StackOverflowError
    at Main.sort(Main.java:10)
    at Main.sort(Main.java:11)
    at Main.sort(Main.java:11)
    ...

For a part of one element, lo = 0, hi = 1: mid = 0, sort(0, 0) returns, but sort(0, 1) calls itself with the same range, forever, until the call stack runs out. Every recursive call must make the problem smaller; a part of size 1 cannot be split, so it must be the base case: if (hi - lo <= 1) return;.

Two lakh numbers

        int n = 200000;
        int[] a = new int[n];
        Random r = new Random(1);
        for (int i = 0; i < n; i++) a[i] = r.nextInt(1000000);
        long t0 = System.nanoTime();
        mergeSort(a);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(a[0] + " " + a[n - 1] + "   " + ms + " ms");

Output: 1 999988 181 ms (bubble sort on the same input: Time Limit Exceeded).

Why merge sort is O(n log n)

  • Levels: the part sizes go n, n/2, n/4, ..., 1, so there are about log₂ n levels (18 for n = 2 × 10⁵).
  • Work per level: all the merges on one level together touch each of the n elements once: O(n).
  • Total: O(n log n), about 3.6 × 10⁶ steps for n = 2 × 10⁵, against 2 × 10¹⁰ for n²/2. That is over 5,000× less work.
  • It is O(n log n) in the best, average and worst case: no input is bad for merge sort.
  • Space: O(n) for tmp, plus O(log n) for the recursion stack. Merge sort is not in-place.

Counting inversions

Brute force: check every pair

    static long countBrute(int[] a) {
        long count = 0;
        for (int i = 0; i < a.length; i++)
            for (int j = i + 1; j < a.length; j++)
                if (a[i] > a[j]) count++;
        return count;
    }

On {5, 1, 4, 2, 8}, {}, {3, 3, 1, 3}, {1, 2, 3, 4, 5}, {5, 4, 3, 2, 1} it printed:

4
0
2
0
10

On two lakh random numbers: Time Limit Exceeded in the compiler. Run locally without a limit, it printed 10017630246 29537 ms: about 30 seconds for 2 × 10¹⁰ pair checks. O(n²).

The key insight: count while you merge

Every inversion is either inside the left half, inside the right half, or a cross pair (one element in each half). The recursion counts the first two. For the cross pairs, look at the merge of two sorted halves:

  • When we take a[j] from the right, it jumps ahead of every element still waiting in the left half, a[i..mid-1]. All of them are bigger than a[j] (the left half is sorted and a[i] > a[j]), and all came before it in the original array. So that is mid - i inversions in one step.
  • Taking from the left jumps over nothing.

Last merge of our example: left [1, 4, 5], right [2, 8]. Taking 2 jumps over 4 and 5: +2 (the pairs (4,2) and (5,2)). The left half [5, 1, 4] contributed 2 more when it was sorted ((5,1) and (5,4)). Total 4.

The optimal solution in Java

    static long count(int[] a) {
        return sort(a, new int[a.length], 0, a.length);
    }
    static long sort(int[] a, int[] tmp, int lo, int hi) {
        if (hi - lo <= 1) return 0;
        int mid = (lo + hi) / 2;
        long count = sort(a, tmp, lo, mid) + sort(a, tmp, mid, hi);
        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;
    }

Same five tests: 4, 0, 2, 0, 10. On the two lakh random numbers: 10017630246 146 ms: the same answer the brute force needed 30 seconds for.

The overflow bug

With int instead of long, on 2 × 10⁵ numbers in reverse order:

        int n = 200000;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = n - i;
        System.out.println(count(a));

int version: -1474936480 (no error, no warning, a wrong answer). The true answer is n(n - 1)/2 = 19,999,900,000, far above Integer.MAX_VALUE = 2,147,483,647, so the int wrapped around (integer overflow). With long: 19999900000.

The same solution in C++

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

// merge sort + inversion count in one pass, on [lo, hi)
long long sortCount(vector<int>& a, vector<int>& tmp, int lo, int hi) {
    if (hi - lo <= 1) return 0;
    int mid = (lo + hi) / 2;
    long long count = sortCount(a, tmp, lo, mid) + sortCount(a, tmp, mid, hi);
    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;
}

long long countInversions(vector<int> a) {          // takes a copy: the caller's array is unchanged
    vector<int> tmp(a.size());
    return sortCount(a, tmp, 0, a.size());
}

void mergeSort(vector<int>& a) {
    vector<int> tmp(a.size());
    sortCount(a, tmp, 0, a.size());                  // sorts a; the count is ignored
}

int main() {
    vector<int> a = {5, 1, 4, 2, 8};
    cout << countInversions(a) << "\n";
    mergeSort(a);
    for (int x : a) cout << x << " ";
    cout << "\n";
    cout << countInversions({}) << " " << countInversions({3, 3, 1, 3}) << " "
         << countInversions({5, 4, 3, 2, 1}) << "\n";
    int n = 200000;
    vector<int> r(n);
    for (int i = 0; i < n; i++) r[i] = n - i;
    cout << countInversions(r) << "\n";
}

Output:

4
1 2 4 5 8 
0 2 10
19999900000

The same solution in Python

import sys

def sort_count(a, tmp, lo, hi):
    """Sorts a[lo:hi] in place and returns its number of inversions."""
    if hi - lo <= 1:
        return 0
    mid = (lo + hi) // 2
    count = sort_count(a, tmp, lo, mid) + sort_count(a, tmp, mid, hi)
    i, j, k = lo, mid, lo
    while i < mid and j < hi:
        if a[i] <= a[j]:
            tmp[k] = a[i]; i += 1
        else:
            count += mid - i
            tmp[k] = a[j]; j += 1
        k += 1
    while i < mid:
        tmp[k] = a[i]; i += 1; k += 1
    while j < hi:
        tmp[k] = a[j]; j += 1; k += 1
    a[lo:hi] = tmp[lo:hi]
    return count

def count_inversions(a):
    a = list(a)                      # work on a copy
    return sort_count(a, [0] * len(a), 0, len(a))

def merge_sort(a):
    sort_count(a, [0] * len(a), 0, len(a))

a = [5, 1, 4, 2, 8]
print(count_inversions(a))
merge_sort(a)
print(a)
print(count_inversions([]), count_inversions([3, 3, 1, 3]), count_inversions([5, 4, 3, 2, 1]))
n = 200000
print(count_inversions(range(n, 0, -1)))

Output:

4
[1, 2, 4, 5, 8]
0 2 10
19999900000

Python's integers never overflow, but recursion depth matters for other recursive code: here the depth is only about log₂ n ≈ 18.

Brute force vs optimal

Approach Time Extra space n = 2 × 10⁵
Check every pair (inversions) O(n²) O(1) 2 × 10¹⁰ steps: TLE (≈ 30 s)
Bubble / selection / insertion sort O(n²) O(1) TLE
Merge sort O(n log n) every case O(n) + O(log n) stack 181 ms
Count inversions while merging O(n log n) O(n) + O(log n) stack 146 ms

Merge sort is stable, not in-place, and not adaptive (sorted input still costs n log n). Java's Arrays.sort on objects uses TimSort, a merge sort variant that is adaptive.

Common mistakes

Mistake What you see Why Fix
if (lo == hi) return; with [lo, hi) Exception in thread "main" java.lang.StackOverflowError a part of size 1 calls itself forever if (hi - lo <= 1) return;
int count for n up to 2 × 10⁵ -1474936480 on reversed input, no error the answer passes 2³¹ - 1 long count (and long return types)
a[i] < a[j] in the counting merge [3, 3, 1, 3] gives 5, not 2 ties take from the right, counting equal pairs a[i] <= a[j]
a[i] < a[j] in plain merge sort still sorted, but unstable equal values swap order <=
Forgetting the two leftover loops elements silently lost / stale values one pile empties first copy the rest of both piles
Forgetting to copy tmp back into a output not sorted the merge result stays in tmp for (k = lo; k < hi; k++) a[k] = tmp[k];
count += mid - i + 1 with half-open ranges counts too many that formula is for an inclusive mid mid - i when the left part is [lo, mid)

Mini project: the movie-taste matcher

Read two friends' rankings of the same n movies (each a permutation of movie ids). Map the first friend's order to positions 0..n-1, build the array of the second friend's positions, and count inversions with merge sort. Print a similarity score 1 - inversions / (n(n - 1)/2) as a percentage. Test it with identical rankings (100%), reversed rankings (0%), and n = 2 × 10⁵ random rankings (it must run in well under a second).

Practice

  1. Count the inversions in [8, 4, 2, 1] by hand, then run it.
Solution

It is reversed, so every pair is an inversion: 4 × 3 / 2 = 6. The program printed 6.

  1. Sort in descending order with merge sort.
Solution

Flip the merge comparison to a[i] >= a[j] (still = for stability). For [5, 1, 4, 2, 8] it printed [8, 5, 4, 2, 1].

  1. Merge two sorted arrays into a new array.
Solution
    static int[] mergeArrays(int[] x, int[] y) {
        int[] out = new int[x.length + y.length];
        int i = 0, j = 0, k = 0;
        while (i < x.length && j < y.length)
            out[k++] = (x[i] <= y[j]) ? x[i++] : y[j++];
        while (i < x.length) out[k++] = x[i++];
        while (j < y.length) out[k++] = y[j++];
        return out;
    }

mergeArrays({1, 4, 5}, {2, 8}) printed [1, 2, 4, 5, 8]. O(n + m) time.

  1. Reverse pairs (hard): count pairs i < j with a[i] > 2 × a[j].
Solution

Same divide and conquer, but count before merging: both halves are sorted, so for each i in the left half move a pointer j forward in the right half while a[i] > 2 × a[j]; j never moves back, so the count is O(n) per level. Use long for 2 × a[j].

    static long reversePairs(int[] a, int[] tmp, int lo, int hi) {
        if (hi - lo <= 1) return 0;
        int mid = (lo + hi) / 2;
        long count = reversePairs(a, tmp, lo, mid) + reversePairs(a, tmp, mid, hi);
        int j = mid;
        for (int i = lo; i < mid; i++) {          // both halves sorted: j only moves forward
            while (j < hi && (long) a[i] > 2L * a[j]) j++;
            count += j - mid;
        }
        int i = lo, k = lo; j = mid;              // normal merge
        while (i < mid && j < hi)
            if (a[i] <= a[j]) tmp[k++] = a[i++];
            else 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;
    }

[1, 3, 2, 3, 1] printed 2; [2, 4, 3, 5, 1] printed 3. O(n log n).

Quick quiz

What does System.out.println(count(new int[]{2, 4, 1, 3, 5})); print?

  • 2
  • 3
  • 4
  • 5
Answer

3: the pairs (2,1), (4,1) and (4,3). In the last merge, [2, 4] with [1, 3, 5]: taking 1 adds 2 (it jumps over 2 and 4), taking 3 adds 1 (it jumps over 4). The program printed 3.

Interview questions

  1. What is the time complexity of merge sort, and why? O(n log n) in every case: log n levels of splitting, O(n) merge work per level.
  2. What is its space complexity? O(n) for the temporary array plus O(log n) recursion stack. It is not in-place (in-place merging exists but is complicated and slow).
  3. Is merge sort stable? Yes, if the merge takes from the left on ties (<=).
  4. Merge sort or quick sort? Merge sort: guaranteed O(n log n), stable, great for linked lists and external sorting (data on disk). Quick sort: in-place and usually faster in memory, but O(n²) worst case (next episode).
  5. How do you count inversions in O(n log n)? Merge sort; whenever the merge takes from the right half, add mid - i.
  6. What does the inversion count tell you? How far the array is from sorted; it equals the number of bubble sort swaps and insertion sort shifts.
  7. Why sort a linked list with merge sort? Merging lists needs no extra array and no random access; splitting uses slow/fast pointers.
  8. What is the maximum inversion count, and which type holds it? n(n - 1)/2; for n = 2 × 10⁵ that is about 2 × 10¹⁰, so long.

Glossary

Term Meaning
Divide and conquer Split a problem into smaller parts, solve them (often recursively), then combine the answers
Recursion / recursive A function that calls itself on a smaller input
Base case The input small enough to answer directly, where the recursion stops (here: size 0 or 1)
Call stack The memory where each active function call is remembered; it is limited
StackOverflowError Java's error when the call stack runs out, usually from recursion that never stops
Merge Combining two sorted sequences into one sorted sequence by repeatedly taking the smaller front element
Merge sort Sort each half recursively, then merge them
Half-open range [lo, hi) lo included, hi excluded; it has hi - lo elements
mid The split point (lo + hi) / 2; the left part is [lo, mid), the right [mid, hi)
Temporary array (tmp) Extra memory the merge writes into before copying back
In-place Uses O(1) extra memory; merge sort is not
Stable Equal values keep their original relative order
Inversion A pair i < j with a[i] > a[j]
Cross pair An inversion with one element in each half
O(n log n) n times log₂ n: 2 × 10⁵ numbers ≈ 3.6 × 10⁶ steps
log₂ n How many times you can halve n before reaching 1 (about 18 for 2 × 10⁵)
Integer overflow A value too big for its type wraps around (int tops out at 2,147,483,647)
long Java's 64-bit integer, up to about 9.2 × 10¹⁸
Kendall tau distance The inversion count between two rankings, used to compare them
Time Limit Exceeded (TLE) Too slow for the judge's limit (8 s in the SyntaxPilot compiler)

Summary

  • Divide and conquer: split the array, sort each half recursively, merge. The base case is a part of size ≤ 1 (hi - lo <= 1); getting it wrong gives StackOverflowError.
  • The merge takes the smaller front element (<= keeps it stable) and copies the leftovers: O(n).
  • Merge sort is O(n log n) in every case and stable, with O(n) extra space: two lakh numbers in milliseconds.
  • Counting inversions is merge sort plus one line: when the merge takes from the right, count += mid - i. O(n log n) instead of O(n²).
  • The count can reach n(n - 1)/2 ≈ 2 × 10¹⁰: use long, or it overflows silently.

Next episode: Quick sort and quickselect: kth largest element.