Solved exercise: counting inversions with merge sort in Java

Solved exam exercise in Java: count out-of-order pairs in an array in O(n log n) by modifying merge sort, with hints, a trace and typical mistakes.

Exam Code Java Algorithms Exam level Tested code

Algorithms and Data Structures · Final examQuestion 4 · 2.5 points · 30 min

A logistics company runs a conveyor belt on which parcels are supposed to pass in non-decreasing order of weight. A sensor records the weight of each parcel in the order it actually passes along the belt. To measure how disordered a batch is, the quality manager defines an out-of-order pair as a pair of positions i < j such that a[i] > a[j]: a heavier parcel passes before a lighter one.

Two parcels with the same weight do not form an out-of-order pair, because non-decreasing order allows them in either relative position. Weights are integers that may be negative (the sensor records deviations from a nominal weight) and may repeat.

Write a Java program that reads the batch from standard input and prints the total number of out-of-order pairs. A quadratic solution that compares every pair will not earn the main marks: you must use an O(n log n) divide-and-conquer algorithm.

Input format. The first line contains an integer n, with 0 ≤ n ≤ 200000. It is followed by n integers separated by spaces or line breaks, each with absolute value at most 10^9. If n is 0, no further values appear.

Output format. A single line with the number of out-of-order pairs, written in decimal and followed by a newline. If there are none, print 0. Think carefully about how large the result can get under these limits.

Below you will find a sample input with six parcels and the output your program must produce. Before you start coding, count the pairs of the sample by hand to make sure you understand the definition, in particular what happens to the two parcels with equal weight.

Sample input

6
3 1 4 1 5 2

Expected output

6

Correct input reading and handling of edge cases (n = 0, n = 1, negative and repeated values)

0.5

Modified merge sort that counts cross pairs during the merge with the correct increment (mid - i) and the correct comparison on ties

1.25

Use of a 64-bit integer type for the counter, with a justification of why int is not enough

0.5

Reasoned analysis of time and space complexity

0.25

Hints

Hint 1 · Which pairs can you count without inspecting them one by one?

Split the array into two halves. Every out-of-order pair lies entirely in the left half, entirely in the right half, or is a cross pair: one element on the left and one on the right. The first two kinds are counted recursively. The real problem is counting the cross pairs in linear time.

Hint 2 · What do you gain if both halves are already sorted?

For counting cross pairs, the internal order of each half does not matter: any element of the left half still comes before any element of the right half. If both halves are sorted and you merge them as in merge sort, then whenever the right element is strictly smaller than the left one, it is also smaller than every element still waiting on the left.

Hint 3 · How much do you add, exactly, and what about ties?

If the merge uses an index i over the left half [lo, mid) and takes an element from the right because it is smaller, there are mid - i left elements greater than it. On a tie you must take the left element first; otherwise you will count parcels of equal weight as out of order.

Solution

Explained solution

The idea is to piggyback on merge sort: sort the array and, along the way, count the out-of-order pairs. Each cross pair is discovered at the exact moment, during the merge, when an element of the right half overtakes the elements still left in the left half. The program reads the data with StreamTokenizer, which is fast and handles negative numbers, and delegates all the work to a recursive method countInversions.

We work with half-open intervals [lo, hi), which makes length arithmetic simpler and avoids the classic off-by-one errors. A single auxiliary array aux is allocated once and reused by every merge.

import java.io.*;

public class Main {

    // Sorts a[lo, hi) and returns the number of out-of-order pairs in that range.
    static long countInversions(int[] a, int[] aux, int lo, int hi) {
        if (hi - lo <= 1) {
            return 0;
        }
        int mid = (lo + hi) >>> 1;
        long inv = countInversions(a, aux, lo, mid) + countInversions(a, aux, mid, hi);
        int i = lo, j = mid, k = lo;
        while (i < mid && j < hi) {
            if (a[i] <= a[j]) {
                aux[k++] = a[i++];
            } else {
                inv += mid - i;
                aux[k++] = a[j++];
            }
        }
        while (i < mid) {
            aux[k++] = a[i++];
        }
        while (j < hi) {
            aux[k++] = a[j++];
        }
        System.arraycopy(aux, lo, a, lo, hi - lo);
        return inv;
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(
                new BufferedReader(new InputStreamReader(System.in)));
        int n = 0;
        if (st.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) st.nval;
        }
        int[] a = new int[n];
        for (int idx = 0; idx < n; idx++) {
            st.nextToken();
            a[idx] = (int) st.nval;
        }
        System.out.println(countInversions(a, new int[n], 0, n));
    }
}

The method countInversions(a, aux, lo, hi) has a two-part contract: when it returns, the range a[lo, hi) is sorted, and the returned value is the number of out-of-order pairs that range contained before it was sorted. The base case is a range of zero or one element, which holds no pairs, so it returns 0. That directly covers the Single parcel and Empty batch tests.

In the recursive case, mid is computed as (lo + hi) >>> 1, which cannot overflow even if the sum exceeds the range of int. The two recursive calls return the pairs internal to each half and leave both halves sorted. This is legitimate because reordering the inside of a half does not change which pairs are cross pairs: every left element still came before every right element in the original array.

The merge walks the left half with i and the right half with j. If a[i] <= a[j], the left element goes to aux and nothing is added. Otherwise a[j] is strictly smaller than a[i] and, since the left half is sorted, also smaller than a[i+1], …, a[mid-1]. So mid - i pairs are added in one go. Each cross pair is counted exactly once: when its right element moves to aux.

The <= comparison is what enforces the statement's rule on equal weights. In the test Repeated values, decreasing, with weights 7 7 3 3 1, the two sevens are not counted against each other, nor are the two threes, and the result is 8: each seven pairs with 3, 3 and 1 (six in total) and each three with the 1 (two more). With < the two ties would also be counted and the program would print 10.

On the sample, 3 1 4 1 5 2, the left half [3, 1, 4] contributes 1 pair (3 with 1) and the right half [1, 5, 2] contributes another (5 with 2). Merging [1, 3, 4] with [1, 2, 5], the left 1 goes first because of the tie; then the right 1 overtakes 3 and 4 (adds 2) and the 2 overtakes the same two (adds 2). Total: 1 + 1 + 4 = 6.

The final loops copy whatever remains in either half; leftovers from the left add nothing, because those pairs were already counted when the right elements left. Finally, System.arraycopy puts the sorted range back into a. In main, if the input is empty, n stays 0, and the Negative values test confirms the reader handles signs: for -1 -5 0 -5 the result is 3.

Code and tests on GitLab

Step-by-step trace · generated by running the code

Step	lo	mid	hi	i	j	inv
1	1	2	3	1	2	0
2	1	2	3	2	3	0
3	0	1	3	0	1	0
4	0	1	3	0	2	1
5	0	1	3	1	3	1
6	4	5	6	4	5	0
7	4	5	6	5	6	1
8	3	4	6	3	4	1
9	3	4	6	4	6	1
10	0	3	6	0	3	2
11	0	3	6	1	3	2
12	0	3	6	1	4	4
13	0	3	6	1	5	6
14	0	3	6	2	5	6
15	0	3	6	3	6	6

Test cases

Case	Input	Expected output	Actual output	Result
Statement example	6 3 1 4 1 5 2	6	6	OK
Already sorted batch	5 1 2 3 4 5	0	0	OK
Repeated values, decreasing	5 7 7 3 3 1	8	8	OK
Negative values	4 -1 -5 0 -5	3	3	OK
Single parcel	1 42	0	0	OK
Empty batch	0	0	0	OK

Actual outputs: code compiled with Java 21.0.12.1 (Temurin) and run in an isolated container on 18 October 2026.

Complexity

Time. The cost satisfies the recurrence T(n) = 2T(n/2) + Θ(n): two calls on half the input and a linear merge in which each comparison does constant work, including the increment inv += mid - i. By the master theorem, T(n) = Θ(n log n). For n = 200000 that is roughly 3.6 million elementary steps, far below the limit. The quadratic version would perform about 2·10^10 comparisons, which is unacceptable.

Memory. Besides the input array, the program uses a single auxiliary array aux of size n, allocated once in main, plus the recursion stack, whose depth is ⌈log₂ n⌉ (about 18 frames at the maximum). In total, Θ(n) extra memory. Allocating a fresh array in every call would not change the asymptotic order, but it multiplies the allocations and the garbage collector's work.

Common mistakes

• Declaring the counter as int: with 200000 weights in strictly decreasing order there are 199999·200000/2 ≈ 2·10^10 pairs, which overflows int without any visible error and produces a meaningless number.
• Using a[i] < a[j] in the merge: on a tie the right element is taken first, and parcels of equal weight are counted as out of order.
• Adding 1 instead of mid - i when a right element is taken, which counts only one of the pairs that element forms with what remains on the left.
• Also adding something in the loops that drain the left leftovers, which counts again pairs that were already recorded.
• Forgetting to copy aux back into a: the halves are not sorted at the level above, and the counts in later merges are wrong.
• Not handling input with n = 0, or computing mid as (lo + hi) / 2 with badly adjusted closed intervals, which causes infinite recursion on ranges of two elements.

Variants

Brute-force reference version

This is the solution many students write first, and it is the one you should use to check the fast one: two nested loops that count every pair i < j with a[i] > a[j]. It costs Θ(n²), so it is only usable on small batches, but it produces exactly the same output on every test and is handy for validating the merge sort version.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(
                new BufferedReader(new InputStreamReader(System.in)));
        int n = 0;
        if (st.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) st.nval;
        }
        int[] a = new int[n];
        for (int idx = 0; idx < n; idx++) {
            st.nextToken();
            a[idx] = (int) st.nval;
        }
        long count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (a[i] > a[j]) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

Counting with a Fenwick tree

Another route to O(n log n): compress the weights to ranks 1..m (sort a copy and remove duplicates) and scan the array from right to left. For each a[i], query a Fenwick tree for how many weights already seen are strictly smaller (prefix up to rank - 1), then insert its rank. It uses the same amount of memory and leaves the original array untouched.

What the professor will ask

“If I know the result can never be negative, why isn't an int enough? And which input produces the maximum value?”

The maximum occurs when the n weights are in strictly decreasing order: every pair is out of order, so there are n(n-1)/2 of them. For n = 200000 that is 19999900000 pairs, almost ten times the largest int (2147483647). The sum would overflow silently and give a wrong value, possibly negative. A long reaches about 9.2·10^18, so it is enough. The sign has nothing to do with it: the problem is the range.

On the syllabus

Merge sort and sorting algorithms have their own block in the syllabus of ISIS1206 Data Structures at Universidad de los Andes (Colombia), and recursion, including converting between recursive and iterative versions, is unit 2 of Algorithms and Programming II (75.41) at Universidad de Buenos Aires. This exercise combines both topics: a recursive merge sort with a counter added to it.

In Chile, the syllabus of Design and Analysis of Algorithms at Universidad de Chile covers merge sort and lower bounds for sorting, and that of IIC2133 at Pontificia Universidad Católica de Chile lists the design and comparison of fundamental data structures, the ground on which the Fenwick tree variant sits.

Opinion · Missing context

What interests me most in this exercise is not merge sort, it is the long. A counter that overflows silently is exactly the kind of bug that passes every small test and breaks on real data. The statement forces you to look at the limits before writing a single line.

The other lesson is about method: the quadratic version is not a mistake, it is the tool for checking the fast one. A student who hands in only the optimised code, with nothing to compare it against, is trusting luck.

Related articles from LaRebelión

Solved exercise: splitting work across threads in JavaSolved exercise: Java serialization with transient fieldsSolved exercise: interfaces, default methods and multiple implementation in Java

• Programming exercises
• Solved exercise: polymorphism and dynamic binding in Java
• Solved exercise: inheritance, constructors and super in Java

Article generated with AI.larebelion

Byline · Chief editor · English edition · London

“The costly bug here is not in the recursion, it is in an int counter nobody sized against the worst case.”