Task: counting inversions - calculating inversion number of a permutation of first n natural numbers — in nlogn.

The most usual approach is to base on merge sort. Not being a fan of this approach, i tried hard to avoid it.

The below is loosely derived/inspired from PM2 Ring's answer from the code with the signature

# Using binary tree counting, derived from C++ code (?) by prasadvk
# https://stackoverflow.com/a/16056139
def ltree_count_PM2R(a):

or more precisely, from the code i wrote firstly in Ada2012, that was loosely derived/inspired from it.
Note: if you want to see that code, you might want to try going back in time in commit history because from some point i was mostly just adapting it to what SPARK2014's prover can do, and that mangled it terribly.

σ[1..n]
tree[1..n]
count_beyond[1..n]
function inserting(root, new)

t := 0
if σ[new] < σ[root] then

t := 1 + count_beyond[root]
branch_side := Left

else

increment count_beyond[root]
branch_side := Right

if tree[root].children[branch_side] ≠ NIL

t := t + inserting(tree[root].children[branch_side], new)

else

tree[root].children[branch_side] := new

return t

function result

var acc := 0
for i := 1 to n loop

acc := acc + inserting(1, i)

return acc

I later were trying to develop a different approach that would make use of having the set be first n natural numbers (the above does not, at all): I thought about taking σ^-1, since it would be suitable for a lookup table because of that, then with the help of it finding, for elements from largest to smallest or vice versa, how many smaller elements (or greater, respectively) (which would be the ones left for processing) were there to the right (or to the left, respectively) of the permutation. I discovered this approach seemed to produce correct results when done by hand, but seems easy to implement.

In 2 5 4 6 3 1 there are 9 inversions.

2 5 4 6 3 1 — 2 smaller on the right side of largest

2 5 4 _ 3 1 — 3 smaller on the right side of largest

2 _ 4 _ 3 1 — 2 smaller on the right side of largest

2 _ _ _ 3 1 — 1 smaller on the right side of largest

2 _ _ _ _ 1 — 1 smaller on the right side of largest

In 3 1 2 4 6 5 there are 3 inversions.

3 1 2 4 6 5 — 1 smaller on the right side of largest

3 1 2 4 _ 5 — 0 smaller on the right side of largest

3 1 2 4 _ _ — 0 smaller on the right side of largest

3 1 2 _ _ _ — 2 smaller on the right side of largest

_ 1 2 _ _ _ — 0 smaller on the right side of largest

There comes the question — is that nlogn like the task asked? What is supposed to be the dominating operation though? Classic approach to this problem is merge sort, and other approaches (like the binary counting tree) do not rely on it being first n natural numbers, and they use comparisons for sorting and it is considering the dominating operation. But we don't need to do any comparisons between the elements of permutation here — but with them being the same first n natural numbers, does that change anything if we were to do comparisons on the indices? The question is, could we do without any number comparisons. And if we couldn't, would it be facilitated to employ some more advanced algorithms to optimize them.

Because, how do we get the information how many smaller (i.e. yet to be processed) are there on the right of our element? When we process the larger, we need a way to store the information about their positions. We could do a naïve boolean lookup table — but maybe something like a heap-like representation of a tree, or simply a two-way list, would be better? Maybe build an order statistic tree? Or maybe some variation of Fenwick Binary Indexed Tree could be derived?