Divide and conquer and the recursion tree in Java

Problem

How many deliveries were swapped

The courier company promises every customer a delivery time. So the orders have a promised order: 1, 2, 3 and so on. The vans drive the way they drive, though, and in the evening the report asks: how far is today's order of deliveries from the promised one?

The measure is the number of swapped pairs: order 5 was delivered before order 3, even though 3 was promised earlier. Such a pair is called an inversion. If the deliveries are exactly in the promised order, there are 0 inversions.

The first solution checks every pair:

static long countPairs(int[] ranks) {
    long inversions = 0;
    for (int i = 0; i < ranks.length; i++) {
        for (int j = i + 1; j < ranks.length; j++) {
            if (ranks[i] > ranks[j]) {
                inversions++;
            }
        }
    }
    return inversions;
}

int[] ranks = {4, 1, 7, 3, 8, 2, 6, 5};
System.out.println("Inversions: " + countPairs(ranks));

Inversions: 12

For 8 orders that is 28 pairs. For n orders it is n(n − 1)/2, so O(n²). The company makes 100,000 deliveries a day, and the pairs are 4,999,950,000. The report that takes a moment in testing runs for minutes in the evening.

The idea

Split, count, combine

The approach is divide and conquer, as in merge sort: split the deliveries into the first half and the second half. Every swapped pair is one of three kinds:

both orders are in the first half;
both are in the second;
one is in the first, the other in the second.

The first two kinds are the same problem, only half as big: the recursion counts them. The hard part is the third kind, the pairs across the halves. If you check each of them, you are back at n².

This is where merging helps. Say both halves are already sorted. When merging you take the smaller of the two first numbers not taken yet. When the smaller one is on the right, every number not taken on the left is bigger than it, and arrived earlier, because it is from the first half. Each of them is one inversion. So one comparison counts as many at once as there are numbers left on the left.

That way the counting "rides on" merge sort: the same splitting, the same merging and one more line.

See it

Counting while merging

sortCount sorts the deliveries in place and returns how many inversions they have. Watch the last merge: every number from the right that goes down counts the numbers not taken on the left:

static long sortCount(int[] ranks) {
    int n = ranks.length;
    if (n <= 1) {
        return 0;
    }
    int mid = n / 2;
    int[] left = Arrays.copyOfRange(ranks, 0, mid);
    int[] right = Arrays.copyOfRange(ranks, mid, n);
    long a = sortCount(left);
    long b = sortCount(right);
    long cross = 0;
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            ranks[k++] = left[i++];
        } else {
            cross += left.length - i;
            ranks[k++] = right[j++];
        }
    }
    while (i < left.length) {
        ranks[k++] = left[i++];
    }
    while (j < right.length) {
        ranks[k++] = right[j++];
    }
    return a + b + cross;
}

Step by step, in words

sortCount gets 8 orders in the order they arrived. Each number is the order's place in the promised order.
mid = 4: the first four deliveries [4, 1, 7, 3] and the last four [8, 2, 6, 5]. Every out-of-order pair is either inside a half or across the two.
Each half calls sortCount on itself: it counts its own pairs (a = 3, b = 4) and comes back sorted.
Now the pairs across. i and j point at the first number not taken yet. 1 < 2: the left one goes down, no inversion.
2 on the right is smaller. Every number left on the left ([3, 4, 7]) is bigger and arrived earlier: left.length - i = 3 inversions at once.
The same rule each time: 5 adds 1, 6 adds 1. cross = 5, after 7 comparisons.
One side has run out. The rest goes to the end without comparing: it adds no inversions.
a + b + cross = 3 + 4 + 5 = 12. The pairs check looks at all 28 pairs; merging finds the same 12 with 17 comparisons in all.

int[] ranks = {4, 1, 7, 3, 8, 2, 6, 5};
System.out.println("Inversions: " + sortCount(ranks));
System.out.println("Sorted: " + Arrays.toString(ranks));

Inversions: 12
Sorted: [1, 2, 3, 4, 5, 6, 7, 8]

The function sorts the array it gets. If you also need the order of the deliveries, pass a copy.

In Java a function cannot return two results without a new class, so sortCount returns the count, and the sorting happens in the array itself. If you want both separately, record Counted(int[] sorted, long count) is a short way.

Try it

Predict the output

The two halves, [2, 4, 6] and [1, 3, 5], are already sorted, so there are no inversions inside them. How many are there across?

static long sortCount(int[] ranks) {
    int n = ranks.length;
    if (n <= 1) {
        return 0;
    }
    int mid = n / 2;
    int[] left = Arrays.copyOfRange(ranks, 0, mid);
    int[] right = Arrays.copyOfRange(ranks, mid, n);
    long a = sortCount(left);
    long b = sortCount(right);
    long cross = 0;
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            ranks[k++] = left[i++];
        } else {
            cross += left.length - i;
            ranks[k++] = right[j++];
        }
    }
    while (i < left.length) {
        ranks[k++] = left[i++];
    }
    while (j < right.length) {
        ranks[k++] = right[j++];
    }
    return a + b + cross;
}

int[] ranks = {2, 4, 6, 1, 3, 5};
System.out.println("Inversions: " + sortCount(ranks));

Answer

Inversions: 6

Inversions: 15

Inversions: 3

The idea

The recursion tree

What does this cost? Draw the calls as a tree. At the top is the call with all n orders. Below it are the two calls it makes, with n/2 each. Below each of them two more, and so on down to the bottom.

Then for every call mark its work: what it does by itself, outside its recursive calls. Here that is the merge: it passes every order the call got once.

Now add it up by levels. At the top the work is n. On the next level there are two calls with n/2 each: n again. Then four with n/4: n again. The levels are how many times n halves down to 1, about log₂ n. So the cost is the levels times the work per level: n · log₂ n.

This is called the recursion tree. It is how you count the cost of any divide and conquer: you do not guess, you add it up level by level.

See it

Three trees, three costs

The same counting for three functions on 8 orders. The binary search from its lesson, written with recursion. Counting by merging. And a third function that also divides, but badly: the first n − 1 orders recursively, and the last one compared with all before it.

static long sortCount(int[] ranks) {
    int n = ranks.length;
    if (n <= 1) {
        return 0;
    }
    int mid = n / 2;
    int[] left = Arrays.copyOfRange(ranks, 0, mid);
    int[] right = Arrays.copyOfRange(ranks, mid, n);
    long a = sortCount(left);
    long b = sortCount(right);
    long cross = 0;
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            ranks[k++] = left[i++];
        } else {
            cross += left.length - i;
            ranks[k++] = right[j++];
        }
    }
    while (i < left.length) {
        ranks[k++] = left[i++];
    }
    while (j < right.length) {
        ranks[k++] = right[j++];
    }
    return a + b + cross;
}

static int find(int[] ranks, int target, int lo, int hi) {
    if (lo > hi) {
        return -1;
    }
    int mid = (lo + hi) / 2;
    if (ranks[mid] == target) {
        return mid;
    }
    if (ranks[mid] < target) {
        return find(ranks, target, mid + 1, hi);
    }
    return find(ranks, target, lo, mid - 1);
}

static long countSlow(int[] ranks, int n) {
    if (n <= 1) {
        return 0;
    }
    long inv = countSlow(ranks, n - 1);
    for (int i = 0; i < n - 1; i++) {
        if (ranks[i] > ranks[n - 1]) {
            inv++;
        }
    }
    return inv;
}

Step by step, in words

Each box is one call, and the number in it is how many orders it gets. find looks at the middle once: work 1.
Then it calls itself on ONE half: 8 → 4 → 2 → 1. One branch, and every level does 1.
4 levels × 1 = 4. The levels are how many times n halves down to 1, about log₂ n: O(log n).
sortCount calls itself on BOTH halves. The merge on top passes all 8 orders; the two below pass 4 + 4 = 8.
Twice as many calls on each level, each with half the orders: the work per level stays 8. The calls with one order only return: 0.
3 levels × 8 = 24: log₂ n levels with n each, O(n log n). For 100 000 orders that is 17 levels, not 100 000.
countSlow also divides, but badly: the first n − 1 orders and the last one. The recursion goes on with n − 1: 8 → 7 → 6 …
On every level the last order is compared with all before it: 7, 6, … 1. 8 levels, and 7 + 6 + 5 + … + 1 = 28: exactly the 28 pairs, O(n²).
The cost is the shape of the tree: levels × work per level. Halving gives log n levels; peeling off one gives n levels. Dividing alone is not enough: the halves must be equal.

int[] sorted = {1, 2, 3, 4, 5, 6, 7, 8};
System.out.println("find: " + find(sorted, 8, 0, sorted.length - 1));
int[] ranks = {4, 1, 7, 3, 8, 2, 6, 5};
System.out.println("countSlow: " + countSlow(ranks, ranks.length));
System.out.println("sortCount: " + sortCount(ranks));

find: 7
countSlow: 12
sortCount: 12

The shape of the tree decides:

One branch, half: log₂ n levels with little work. O(log n).
Two branches, halves: log₂ n levels of n. O(n log n).
One branch, one smaller: n levels of n. O(n²). That is checking pairs, only written with recursion.

The same happens in quick sort with a bad pivot: on sorted input the pivot splits off one price, and the other n − 1 stay in one part. The tree is a chain of n levels, and the complexity is n².

See it

Measure it: by pairs against by merging

Run both on the same deliveries. For pairs we count the pairs checked, for merging the comparisons. By pairs at 100,000 does not really run: Bench estimates it from the curve.

Inversions by pairs O(n²)
Inversions by merging O(n log n)

Algorithm	n = 10	n = 1,000	n = 10,000	n = 100,000
Inversions by pairs	45	499,500	49,995,000	≈ 4,999,500,000
Inversions by merging	21	8,693	120,553	1,536,329

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

static long sortCount(int[] ranks) {
    int n = ranks.length;
    if (n <= 1) {
        return 0;
    }
    int mid = n / 2;
    int[] left = Arrays.copyOfRange(ranks, 0, mid);
    int[] right = Arrays.copyOfRange(ranks, mid, n);
    long a = sortCount(left);
    long b = sortCount(right);
    long cross = 0;
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            ranks[k++] = left[i++];
        } else {
            cross += left.length - i;
            ranks[k++] = right[j++];
        }
    }
    while (i < left.length) {
        ranks[k++] = left[i++];
    }
    while (j < right.length) {
        ranks[k++] = right[j++];
    }
    return a + b + cross;
}

With 1000 deliveries the pairs are 499,500, and the comparisons 8,693. At 100,000 merging makes 1,536,329 comparisons against 4,999,950,000 pairs: over 3000 times fewer. And the inversions are the same, 2,504,458,463.

More precisely, if you are curious

The same numbers in your language. The deliveries are shuffled with a small seeded generator, so they are the same on every run, in every language and in Bench:

static long checks = 0;
static long comparisons = 0;

static int[] deliveries(int n) {
    int[] ranks = new int[n];
    for (int k = 0; k < n; k++) {
        ranks[k] = k + 1;
    }
    long x = 2026;
    for (int k = n - 1; k > 0; k--) {
        x = x * 48271 % 2147483647;
        int j = (int) (x % (k + 1));
        int t = ranks[k];
        ranks[k] = ranks[j];
        ranks[j] = t;
    }
    return ranks;
}

static long countPairs(int[] ranks) {
    long inversions = 0;
    for (int i = 0; i < ranks.length; i++) {
        for (int j = i + 1; j < ranks.length; j++) {
            checks++;
            if (ranks[i] > ranks[j]) {
                inversions++;
            }
        }
    }
    return inversions;
}

static long sortCount(int[] ranks) {
    int n = ranks.length;
    if (n <= 1) {
        return 0;
    }
    int mid = n / 2;
    int[] left = Arrays.copyOfRange(ranks, 0, mid);
    int[] right = Arrays.copyOfRange(ranks, mid, n);
    long a = sortCount(left);
    long b = sortCount(right);
    long cross = 0;
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        comparisons++;
        if (left[i] <= right[j]) {
            ranks[k++] = left[i++];
        } else {
            cross += left.length - i;
            ranks[k++] = right[j++];
        }
    }
    while (i < left.length) {
        ranks[k++] = left[i++];
    }
    while (j < right.length) {
        ranks[k++] = right[j++];
    }
    return a + b + cross;
}

for (int n : new int[] {10, 1000}) {
    checks = 0;
    long inv = countPairs(deliveries(n));
    System.out.println("by pairs, n = " + n + ": " + checks + " checks, " + inv + " inversions");
}
for (int n : new int[] {10, 1000, 100000}) {
    comparisons = 0;
    long inv = sortCount(deliveries(n));
    System.out.println("by merging, n = " + n + ": " + comparisons + " comparisons, " + inv + " inversions");
}

by pairs, n = 10: 45 checks, 14 inversions
by pairs, n = 1000: 499500 checks, 249193 inversions
by merging, n = 10: 21 comparisons, 14 inversions
by merging, n = 1000: 8693 comparisons, 249193 inversions
by merging, n = 100000: 1536329 comparisons, 2504458463 inversions

The inversions at 100,000 are over 2.5 billion, and an int stops at 2,147,483,647. That is why the counters are long. With int the number would wrap around and come out negative, without any error.

Try it

Find the bug

A colleague has rewritten the function. For the 8 deliveries from the scene it says 5 instead of 12:

int[] ranks = {4, 1, 7, 3, 8, 2, 6, 5};
System.out.println("Inversions: " + sortCount(ranks));
System.out.println("Sorted: " + Arrays.toString(ranks));

Inversions: 5
Sorted: [1, 2, 3, 4, 5, 6, 7, 8]

Which line is the bug on?

Pick the line with the bug.

Try it

Fill in

The number on the right is smaller and goes down. By how much does cross grow?

static long sortCount(int[] ranks) {
    int n = ranks.length;
    if (n <= 1) {
        return 0;
    }
    int mid = n / 2;
    int[] left = Arrays.copyOfRange(ranks, 0, mid);
    int[] right = Arrays.copyOfRange(ranks, mid, n);
    long a = sortCount(left);
    long b = sortCount(right);
    long cross = 0;
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            ranks[k++] = left[i++];
        } else {
            cross += ;
            ranks[k++] = right[j++];
        }
    }
    while (i < left.length) {
        ranks[k++] = left[i++];
    }
    while (j < right.length) {
        ranks[k++] = right[j++];
    }
    return a + b + cross;
}

Exercise

The daily report

Solve it in your editor.

Swapped pairs. Read the order of the deliveries (the promised numbers, separated by spaces) and print how many pairs are swapped and out of how many. Use sortCount from the lesson.

3 1 2 6 4 5 10 7 9 8

Swapped pairs: 8 of 45

More tasks

Draw the tree. A function splits its input into three equal parts and calls itself on each, and its work outside the calls is n. Draw the levels: how many are there, and what is the work per level? And if there are two parts, but the work of each call is n²?
Who is delayed the most. For every order count how many orders with a bigger number were delivered before it. The sum of these numbers is the number of inversions. How do you collect them while merging? Hint: when a number goes down from the right, the numbers not taken on the left count for it.
Is it nearly sorted. Count the inversions in an order that is nearly sorted (two neighbouring orders swapped). How many comparisons does merging make? And insertion sort from the simple sorts on the same input?

More precisely

The master theorem and the other languages

The recursion tree works for any divide and conquer. For the most common kind there is also a ready rule.

More precisely, if you are curious

The master theorem, as intuition. A function that splits its input into b equal parts, calls itself a times and does work f(n) outside the calls is written as T(n) = a · T(n/b) + f(n). Draw the tree and compare the work at the top with the work at the bottom:

The work is the same on every level. You multiply by the number of levels, log n. Merge sort: T(n) = 2 · T(n/2) + n, n per level, O(n log n). Binary search: T(n) = T(n/2) + 1, 1 per level, O(log n).
The work shrinks going down. The top level decides. T(n) = 2 · T(n/2) + n² is O(n²): the lower levels are n²/2, n²/4 and so on, and their sum is below one more n².
The work grows going down. The leaves decide. Karatsuba's multiplication of big numbers is T(n) = 3 · T(n/2) + n: three halves on every level, the work grows by 3/2 per level, and the complexity is about n^1.58 instead of the n² of school multiplication.

The bad split T(n) = T(n − 1) + n is not of this kind at all: the input is not divided by b, it shrinks by one. The theorem does not help there, but the tree does: n levels of about n, O(n²).

The maths behind it is in every algorithms textbook. For work the picture is enough: how many levels and how much work per level.

How deep the recursion goes. The call stack is as tall as the levels of the tree. Counting by merging is 17 levels for 100,000 orders and fits everywhere. The bad split is n levels.

Java, C# and JavaScript have no limit on the number of levels, but their stack is about 1 MB. With 100,000 nested calls it runs out too, as in quick sort with a bad pivot. In Python the limit is 1000 levels, and the bad split falls over already at about 1000 orders.

Inversions as a measure. The number of inversions between two orderings measures how much they differ: that is how rankings are compared, for example a search engine's results against people's ratings. Insertion sort makes exactly as many moves as its input has inversions. That is why it is fast on nearly sorted input and slow on shuffled input.

Test

Check yourself

1. The recursion tree of a function has log₂ n levels, and the work on every level is n in total. What is the cost?O(log n)O(n log n)O(n)

2. A function calls itself once, on half of its input, and does constant work. What is the cost?O(log n)O(n)O(n log n)

3. A function splits its input into the first n − 1 and the last one, calls itself on the n − 1 and compares the last one with all the others. What is the cost?O(n²)O(n)O(n log n)

4. While merging, the number on the right is smaller, and 3 numbers on the left are not taken yet. How many inversions does this take add?301

5. Why is the number of inversions a long and not an int in Java and C#?long is faster than intBecause merging only works with longWith 100,000 orders the inversions can be about 2.5 billion, and an int stops at about 2.1 billion

Divide and conquer and the recursion tree

Cookies