[ACCEPTED]-calculating the number of “inversions” in a permutation-complexity-theory

You can use the merge sort algorithm.

In the merge 15 algorithm's loop, the left and right halves 14 are both sorted ascendingly, and we want 13 to merge them into a single sorted array. Note 12 that all the elements in the right side 11 have higher indexes than those in the left 10 side.

Assume array[leftIndex] > array[rightIndex]. This means that all elements 9 in the left part following the element with 8 index leftIndex are also larger than the current 7 one in the right side (because the left 6 side is sorted ascendingly). So the current 5 element in the right side generates numberOfElementsInTheLeftSide - leftIndex + 1 inversions, so 4 add this to your global inversion count.

Once 3 the algorithm finishes executing you have 2 your answer, and merge sort is O(n log n) in the worst 1 case.

There is an article published in SIAM in 24 2010 by Cham and Patrascu entitled Counting Inversions, Offline Orthogonal Range Counting, and Related Problems that 23 gives an algorithm taking O(n sqrt(log(n))) time. This 22 is currently the best known algorithm, and 21 improves the long-standing O(n log(n) / log(log(n))) algorithm. From 20 the abstract:

We give an O(n sqrt(lg n))-time algorithm for 19 counting the number of inversions in a 18 permutation on n elements. This improves 17 a long-standing previous bound of O(n lg n / lg lg n) that followed 16 from Dietz's data structure [WADS'89], and 15 answers a question of Andersson and Petersson 14 [SODA'95]. As Dietz's result is known 13 to be optimal for the related dynamic 12 rank problem, our result demonstrates 11 a significant improvement in the offline setting.

Our 10 new technique is quite simple: we perform 9 a "vertical partitioning" of a trie 8 (akin to van Emde Boas trees), and use 7 ideas from external memory. However, the 6 technique finds numerous applications: for 5 example, we obtain

• in d dimensions, an algorithm to answer n offline orthogonal range counting queries in time O(n lg^d-2+1/d n);
• an improved construction time for online data structures for orthogonal range counting;
• an improved update time for the partial sums problem;
• faster Word RAM algorithms for finding the maximum depth in an arrangement of axis-aligned rectangles, and for the slope selection problem.

As a bonus, we also 4 give a simple (1 + ε)-approximation algorithm 3 for counting inversions that runs in linear 2 time, improving the previous O(n lg lg n) bound by 1 Andersson and Petersson.

I think the awesomest way to do this (and 27 thats just because I love the data structure) is 26 to use a binary indexed tree. Mind you, if all you need is 25 a solution, merge sort would work just as 24 well (I just think this concept totally 23 rocks!). The basic idea is this: Build a 22 data structure which updates values in O(log 21 n) and answers the query "How many 20 numbers less than x have already occurred 19 in the array so far?" Given this, you 18 can easily answer how many are greater than 17 x which contributes to inversions with x 16 as the second number in the pair. For example, consider 15 the list {3, 4, 1, 2}.

When processing 3, there's 14 no other numbers so far, so inversions with 13 3 on the right side = 0 When processing 12 4, the number of numbers less than 4 so 11 far = 1, thus number of greater numbers 10 (and hence inversions) = 0 Now, when processing 9 1, number of numbers less than 1 = 0, this 8 number of greater numbers = 2 which contributes 7 to two inversions (3,1) and (4,1). Same 6 logic applies to 2 which finds 1 number 5 less than it and hence 2 greater than it.

Now, the 4 only question is to understand how these 3 updates and queries happen in log n. The 2 url mentioned above is one of the best tutorials 1 I've read on the subject.

These are the original MERGE and MERGE-SORT 13 algorithms from Cormen, Leiserson, Rivest, Stein 12 Introduction to Algorithms:

MERGE(A,p,q,r)
 1  n1 = q - p + 1
 2  n2 = r - q
 3  let L[1..n1 + 1] and R[1..n2 + 1] be new arrays
 4  for i = 1 to n1
 5      L[i] = A[p + i - 1]
 6  for j = 1 to n2
 7      R[j] = A[q + j]
 8  L[n1 + 1] = infinity
 9  R[n2 + 1] = infinity
10  i = 1
11  j = 1
12  for k = p to r
13      if L[i] <= R[j] 
14          A[k] = L[i]
15          i = i + 1
16      else A[k] = R[j]
17          j = j + 1

and

MERGE-SORT(A,p,r)
 1 if p < r
 2     q = floor((p + r)/2)
 3     MERGE-SORT(A,p,q)
 4     MERGE-SORT(A,q + 1,r)
 5     MERGE(A,p,q,r)

at line 8 11 and 9 in MERGE infinity is the so called 10 sentinel card, which has such value that 9 all array elements are smaller then it. To 8 get the number of inversion one can introduce 7 a global counter, let's say ninv initialized 6 to zero before calling MERGE-SORT and than 5 to modify the MERGE algorithm by adding 4 one line in the else statement after line 3 16, something like

ninv += n1 - i

than after MERGE-SORT 2 is finished ninv will hold the number of 1 inversions