I am trying to count inversion in a array (two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j). I know that is easily possible to resolve these problems using brute force in O(n^2) and by using Divide and Conquer in O(nlgn).
My Question was that is it possible to use a form of bucketing technique to achieve an efficiency of O(n) with knowledge about the data. For instance I already know that the array is a permutation of 1-32 , thus the maximum element is 32 (entailing that we can do something with bucketing).
I have been thinking about this and noticed that if we are inserting an element in a bucket, then the sum of all buckets greater than it at the time of insertion is its inversion count. But if we add the number of elements in each bucket every time, then it causes me to lose the O(n) efficiency. Any suggestions of how to keep a count to remove this penalty.
Please note that the permutation can be of any length, but during execution we know the number of elements in the permutation. Thus the value of "n" is known during execution and the permutation consists of elements from "1" to "n".
Sorting : It is possible to sort this data set in O(n) time complexity, as we can create 32 buckets and we know that each bucket will have exactly one element. Thus the efficiency of bucket sort which is O(n + M) is O(n + 1) = O(n) for this specific example.
According to http://arxiv.org/pdf/1503.01192.pdf it is "well known" that you cannot find the number of inversions more efficiently than O(n log n).