# Counting inversions

Given a table, find for every entry how many elements there are to left that are larger and how many elements there are to right that are smaller. In other words find out how many swaps bubble sort will do on the table.

## A \(O(n\log n)\) algorithm based on merge sort

Consider one step of the recursive merge sort applied on the table. In the merge step we are given two consecutive portions of the table which each are already sorted. A temporary table recieves the result of the merging of the two lists. We have two pointers i and j that progress in each of the tables and a pointer k in the temporary table.

At any moment we compare the elements pointed by i and j and move the smaller of them to the temporary table. In each of the cases we can identify some inversion pairs as depicted below.

In the implementation below, we do not sort the intial given table, but rather a vector *rank* containing indices to the table. This is necessary since otherwise the items would at some stage of the algorithm not be at their initial position anymore, making it impossible to increase the correct entries in the tables *left* and *right*