This example uses a recursive algorithm similar to mergesort to solve the inversion counting problem. For other interesting algorithms, see my book Essential Algorithms, Second Edition. The book describes many fascinating algorithms in pseudocode with source code available for download in Python and C#.

Title: Solve the inversion counting problem in Python

[This program shows two methods for solving the inversion counting problem in Python.]

This example uses an interesting algorithm to solve the inversion counting problem in Python. It's very similar to the mergesort algorithm described in my book Essential Algorithms, Second Edition.

An inversion in a list occurs when two values are out of order. More precisely, if value[a] > value[b] and a < b, then those two values are out of order and count as an inversion.

For example, the list [1, 4, 3, 2, 5] has 3 inversions: {4, 3}, {4, 2}, and {3, 2}.

In the inversion counting problem, the goal is to count the number of inversions in a list.

This example demonstrates two approaches: a simple O(N²) algorithm and a more complicated but faster O(N log N) approach.

O(N²) Algorithm

One very simple solution is to loop through each item in the array. For each item A, you loop through the following items and count the number of items that are smaller than the A. The following code shows how the program implements this simple algorithm.

def count_inversions_n2(values): '''Count inversions the simple O(N^2) way.''' num_values = len(values) count = 0 for i in range(num_values - 1): for j in range(i + 1, num_values): if values[i] > values[j]: count += 1 return count

That works, but it takes O(N²) time where N is the size of the array. That's fast enough for practical purposes, but we can do better. Before I describe that algorithm, however, you should know a bit about mergesort.

Mergesort

Mergesort is one of many O(N log N) sorting algorithms. The way it works is it first splits the list into two equally sized pieces. It then recursively calls itself to split the pieces into smaller and smaller chunks. When a piece contains a single item, that piece is already sorted. (Because a single item is always in sorted order.)

As the recursions return, the algorithm merges the sorted sub-pieces to make bigger and bigger sorted pieces until the entire array is sorted.

For example, consider these values:

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

The algorithm first splits this into two pieces:

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

Next it recursively splits those pieces:

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

And it recursively splits the pieces again:

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

At this point, each of the sub-lists is sorted because it contains a single item.

Now the last recursive calls return and merge their sub-lists. For example, the calls that reached sub-lists [3] and [5] return and the calling code merges those sub-lists to get [3, 5]. This is no big deal because those items were already in order.

Similarly the calls that reached [2] and [7] return and the calling code merges them to get [7, 2]. This time the merge code had to rearrange the 2 and 7 to put them in the right order.

The remaining calls at this level merge sub-lists to get [1, 4] and [6, 8].

Now those calls return and the higher-level calls merge the new sub-lists. The values [3, 5] and [2, 7] merge to get [2, 3, 5, 7]. Similarly the values [4, 1] and [6, 8] merge to get [1, 4, 6, 8].

Finally the first call to the algorithm merges its sub-lists to get [1, 2, 3, 4, 5, 6, 7, 8].

O(N log N) Algorithm

The inversion counting algorithm follows a similar approach.

First, here's the method that recursively splits the array into smaller and smaller pieces.

def mergesort_and_count(values, count=0): num_values = len(values) if num_values > 1: # Split it. m = num_values // 2 count, left = mergesort_and_count(values[:m], count) count, right = mergesort_and_count(values[m:], count) count, values = merge_and_count(left, right, count) return count, values

The parameters are the list values and the count of inversions found so far by other calls to the function. When it finishes, the function returns the sorted list and the number of inversions it found.

The code first saves the length of values in a variable for convenience. Then, if the number of items in the values list is greater than 1, the code splits the list into left and right halves. It recursively calls itself to count the inversions in those left and right halves and saves the sorted halves and the updated inversion count in local variables.

Having sorted the two halves, the function calls merge_and_count to merge the two halves. That function returns the merged sorted list and the updated number of inversions it found.

After it's done merging the sub-lists, the mergesort_and_count function returns its sorted sub-list and count. The method finishes by returning its count.

The following code shows the merge_and_count function.

def merge_and_count(left, right, count): '''Merge the pieces and return the number of inversions.''' # Merge. values = [] while len(left) > 0 and len(right) > 0: if left[0] <= right[0]: values.append(left.pop(0)) else: values.append(right.pop(0)) count += len(left) # Copy remaining items. if len(left) > 0: values.extend(left) elif len(right) > 0: values.extend(right) return count, values

This function first creates a values list to hold the sorted values. Then, as long as both the left and right sub-lists are non-empty, the method checks the first items in both lists to see which is smaller. If the left item is smaller, the code simply moves it into the values list.

If the right item is smaller, then is has mistakenly been placed after all of the remaining items in the left list. It is smaller than all of those items, so each of them represents an inversion. The code moves the item into the values list and then increases the inversion count by the number of items in the left list.

When either the left or right sub-list is empty, the code adds the remaining items from the other list into values.

After it finishes, the function returns the now sorted list and the updated inversion count.

Test Program

The following code shows a test program that invokes the O(N²) and O(N log N) functions.

import random import time def generate_list(num_values): max_value = 2 * num_values values = [] for i in range(num_values): values.append(random.randrange(max_value)) return values # Generate the list. values = generate_list(10000) start_time = time.time() num_inversions = count_inversions_n2(values) stop_time = time.time() elapsed1 = stop_time - start_time print(f'{num_inversions} inversions, {elapsed1} seconds') start_time = time.time() num_inversions, values = mergesort_and_count(values) stop_time = time.time() elapsed2 = stop_time - start_time print(f'{num_inversions} inversions, {elapsed2} seconds') print(f'Method 1 takes {elapsed1 / elapsed2:.0f} times as long') print(f'Method 2 takes {elapsed2 / elapsed1:.2%} as long')

This code defines a generate_list function that creates a list of random values. It then uses that function to make a random list holding 10,000 items.

The code calls count_inversions_n2 to count the inversions, and then displays the number of inversions and the elapsed time.

The program then repeats those steps using the mergesort_and_count function.

Here's the result:

25111133 inversions, 2.2747836112976074 seconds 25111133 inversions, 0.08661222457885742 seconds Method 1 takes 26 times as long Method 2 takes 3.81% as long

As you can see, the mergesort-like algorithm is much faster.

If you perform a bunch of experiments with lists of different sizes, you probably won't see the O(N log N) performance promised by the second approach. There's a fair amount of overhead in Python's splitting and rearranging lists and I suspect that limits the function's performance. You can get better results in languages like C++ and C# where you can use arrays instead of lists.

Download the example to see all of the details.

Title: Solve the inversion counting problem in Python

O(N2) Algorithm

Mergesort

O(N log N) Algorithm

Test Program

O(N²) Algorithm