Counting Inversions with Merge Sort

In my last blog post I ended with Merge Sort and briefly mentioned inversion counting and that it can be useful for a simple recommendation engine. I wanted to explain this in a little more detail and give a proof of concept example.

First of all, inversions are pairs of numbers, in a disordered list, where the larger of the two numbers is to the left of smaller number. In the following list: [ 1, 3, 5, 2, 4, 6 ] there are 3 inversions: (3,2), (5,2), and (5,4). We can visualize this like so:

By drawing lines between matching numbers in the disordered list and it’s ordered counterpart we create a series of crossed lines which correspond to each of the inversions. These inversions show the degree to which our list is out of order. If we have a good way to count inversions then we can map values to numbers and make comparisons between lists of values.

For example, if I wanted to find who in a group I most share the same hobbies with I could have everyone rank hobbies, map them to values based on my hobbies to establish an order, and run them through an inversion counting algorithm to see who’s hobbies most match mine. We would probably have to do a little extra cleanup work to get matching sets of data but after that it could look like this:

I have 4 inversions with person A and 2 inversions with person B. So it looks like I should hangout with Person B.

We can achieve this by hand drawing the sorted and unsorted lists, but lets look at how we can do this programmatically, and for free, using Merge Sort. Lets briefly review Merge Sort:

#!/usr/bin/env python
def mergeSort(arr):
    if len(arr) == 1:
        return arr
    else:
        a = arr[:len(arr)/2]
        b = arr[len(arr)/2:]
        a = mergeSort(a)
        b = mergeSort(b)
        c = []
        i = 0
        j = 0
        while i < len(a) and j < len(b):
            if a[i] < b[j]:
                c.append(a[i])
                i = i + 1
            else:
                c.append(b[j])
                j = j + 1
        c += a[i:]
        c += b[j:]
    return c

First we recursively split the input list in half into ‘a’ and ‘b’. Once we have recursed log2(n) times and get to single element lists and hit our base case. Now we work our way back up the recursion tree. At each level of recursion, the lists returned as ‘a’ and ‘b’ are iterated through and appended to ‘c’ such that ‘c’ is a sorted array.

Because the elements of ‘a’ and ‘b’ are appended to ‘c’ in order of least to greatest, and ‘a’ and ‘b’ are the list ‘c’ from the last returned recursive calls, ‘a’ and ‘b’ are always sorted. At each recursive step we compare the lowest values from ‘a’ and ‘b’, appending the lower value to ‘c’ and incrementing the iterator for the array which was the source of the appended value. Because ‘a’ and ‘b’ are already sorted, once one array is fully iterated and added to ‘c’ we can dump the entire remainder of the other array into ‘c’ as well.

Now recall that an inversion is a a pair of numbers where the higher number comes before the lower number. This is precisely what is going on in Merge Sort when we combine ‘a’ and ‘b’. There are no inversions within ‘a’ or ‘b’ individually but there are inversions between ‘a’ and ‘b’. The conditional is checking for these inversions and correcting them as the elements are added to ‘c’.

So now we know when the inversions are being corrected. We need to know how many inversions are being corrected these moments. Consider the following example:

a = [ 1, 3, 5 ]
b = [ 2, 4, 6 ]

Both lists are sorted individually and but there are inversions between them. The first value in ‘b’ is 2 and makes up two inversions (3,2) and (5,2). Merge Sort will correct this like so:

i = 0
j = 0
a = [ 1, 3, 5 ]
b = [ 2, 4, 6 ]
1. a[i] is smaller then b[j] so a[i] is appended to ‘c’ and ‘i’ is incremented. 
c = [ 1 ]
i = 1, j = 0
2. a[i] is greater then b[j] so b[j] is appended to ‘c’ and ‘j’ is incremented. 
c = [ 1, 2 ]
i = 1, j = 1
3. a[i] is smaller then b[j] so a[i] is appended to ‘c’ and ‘i’ is incremented. 
c = [ 1, 2, 3]
1 = 2, j = 1
and so on…

All elements from ‘a’ that are smaller then b[j] are added to ‘c’ before b[j]. In other words, the amount of numbers in ‘a’ that are bigger then b[j] is the amount of numbers in ‘a’ which have not been appended to ‘c’ yet. We now know that b[j] is in an inversion pair with each element of ‘a’ that has not been appended to ‘c’. We also know that there are no inversions in ‘b’ because ‘b’ is already sorted! Thus we know exactly how many inversions b[j] is a part of.

The iterator ‘i’ already tracks how many elements in ‘a’ have been appended to ‘c’ so all we have to do is subtract ‘i’ from the length of ‘a’ and we get this number of inversions involving b[j]. If we keep a running tally of len(a)-i for every time an element from ‘b’ is smaller then an element in ‘a’ then we know the total number of inversions between ‘a’ and ‘b’.

We need to pass this value along between the levels of recursion to get the total inversions in the input. We do this by returning it with ‘c’, and end up with something like this:

#!/usr/bin/env python
import os, sys
def mergeSortInversions(arr):
    if len(arr) == 1:
        return arr, 0
    else:
        a = arr[:len(arr)/2]
        b = arr[len(arr)/2:]
        a, ai = mergeSortInversions(a)
        b, bi = mergeSortInversions(b)
        c = []
        i = 0
        j = 0
        inversions = 0 + ai + bi
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1
            inversions += (len(a)-i)
    c += a[i:]
    c += b[j:]
return c, inversions

Notice that this is essentially the exact same algorithm as earlier on. Merge Sort was already counting inversions for us, we just needed to track it. Merge Sort with inversion counting, just like regular Merge Sort, is O(n log(n)) time.

With our inversion counting algorithm dialed in, we can go back to our recommendation engine hypothetical. All we need is a hash table to translate hobbies to integers where your hobby ranking is ordered 1..n. Use the hash table to translate other people’s hobby rankings into unordered lists (and filter out hobbies we don’t share) and process them with Merge Sort. The person with least inversions will have the closest matching set of hobbies.

Of course, such a recommendation engine will have a number of problems in the real world. However, it is an interesting use of what is essentially a side effect of a common sorting algorithm. I’ll leave the implementation of this up to the reader.