Fast algorithm for computing the orders of all elements in an array?

Suppose that you're given an array A of n distinct elements drawn from some totally-ordered set. For example, you might be given

137 13 7 42 38

The goal is to produce for this array of elements a matching array B such that B[i] is the number of elements in the original array that are smaller than A[i]. For example, in the above array, we'd want to produce

A = 137  13   7  42  38
B =   4   1   0   3   2

Since 137 is bigger than four other elements (13, 7, 42, 38), 13 is o开发者_Go百科nly bigger than one of the elements (7), 7 is bigger than no other elements, etc.

In the most general case, where the elements in the array are arbitrary objects that can only be compared, any solution to this problem must run in Ω(n lg n) in the worst case because once we have this table, we can sort the array in O(n) time by making a new array of n elements, then putting each element in the position specified in the table. However, what I don't know is how fast we can construct this table when the elements are not arbitrary values.

My question is this: suppose that you're given an array of n distinct integer values and want to construct a table of order statistics for that array. What is the most efficient algorithm for doing so? If it helps, you can assume the integers are positive and that the largest of them has value U.

Currently, the best I have is an O(n lg n) solution that works by making a copy of the array, sort it, then for each integer in the original array, doing a binary search to find its position in the new array. This is a fine solution, but I was really hoping that there would be some better way of doing this.

---

Step 1: sort the original array indexes.

A  = 137  13   7  42  38
I  =   0   1   2   3   4

A' =   7  13  38  42 137
I' =   2   1   4   3   0

Step 2: for every I'[i] = j assign B[j] = i.

I' =   2   1   4   3   0
i  =   0   1   2   3   4

B  =   4   1   0   3   2

---

There is at least no comparison-based approach to this problem that does better than O(n log n), which is a general lower bound for comparison-based sorting. (Otherwise you could apply the new magical procedure and afterwards iterate over B to construct a sorted version of A).

If the integers of your input array A however are restricted to some known range, say [1..M], then you can do better - i.e. O(M + n) - by marking those numbers (in an array, say L[1..M]), which occur in A, remember their position in A and afterwards to a sweep through L from index 1..M to construct B.

---

This doesn't improve the big-O, but your algorithm does 2 different N-LogN operations. Instead of sorting the array itself, sort an array of {value, originalIndex} structures.

Then walk through the sorted array doing rank[sorted[i].originalIndex]=i;

This is only 1 N-LogN operation.

And with a max bound on U, you could do a radix sort to get O(kN) instead (assuming you have the memory)

---

Most likely you want to make all combinations of the first array with n^2-n and then compare each element with the other to find the 1st number and repeat this with every number of the 1st array using a 2nd array to count.

---

A way to do it is using prefix sums