CODEWITHSUNDEEP
algorithmsortinglanguage-agnostic
Luiz Rodrigo
Luiz Rodrigo

Reputation: 936

Optimal inversion counting on int arrays

Today I was looking the latest exam of the local informatics olympiad and I found a interesting problem. Briefly, it asks to, given an integer array, count how many inversions it has, where an inversion is a pair of indicies i, j such that i > j and A[i] < A[j]. Informally, the number of inversions is the number of pairs that are out of order. Initially I made a O(n²) solution (yes, the naive one), but seeing it wouldn't fit well with the size of the input, I thought about the problem a bit more and then I realized it's possible to do it within O(n log n) time by a variant of merge sort, which handles good the size of the input.

But seeing the input constraints (n integers between 1 and M, and no duplicates), I was wondering if my solution is optimal, or do you know if is there any other solution to this problem that beats O(n log n) runtime?

Upvotes: 8

Views: 1044

Answers (3)

therealsachin
therealsachin

Reputation: 1684

If we assume the number of bits used to represent the integer is constant (say 32 or 64 bits), this can be solved in O(N) time.

Here is an example python implementation.

http://ideone.com/g57O87


def inv_count(a, m=(1<<32)):
  if not m or not a:
      return 0
  count = 0
  ones = []
  zeros = []
  for n in a:
    if n & m:
      ones.append(n & ~m)
    else:
      count += len(ones)
      zeros.append(n & ~m)
  m /= 2
  return count + inv_count(ones, m) + inv_count(zeros, m)



print inv_count([1, 2, 3, 4, 5])
print inv_count([5, 4, 3, 2, 1])

We are able to achieve less than O(N x Log(N)) time complexity, as we are using idea behind a non-comparative sorting algorithm, radix sort, to get the count.

Upvotes: 0

banarun
banarun

Reputation: 2321

O(n log n) is the best as far as I know.

A detailed explanation was given here:

http://www.geeksforgeeks.org/counting-inversions/

Upvotes: 1

slowpoke
slowpoke

Reputation: 121

The best result in the literature is an O(n √(log n)) algorithm due to Chan and Patrascu. No idea about the constant.

Upvotes: 5

Related Questions