TAOCP 5.1 Exercise 3
Store the permutation in an array $P$ such that $P(j)$ is the position of $j$ in the permutation.
Section 5.1: Combinatorial Properties of Permutations
Exercise 3. [**] [26] Design an algorithm that computes the inversion table $b_1 b_2 \dots b_n$ corresponding to a given permutation $a_1 a_2 \dots a_n$ of ${1,2,\dots,n}$, where the running time is essentially proportional to $n \log n$ on typical computers.
Verified: yes
Solve time: 18m15s
Store the permutation in an array $P$ such that $P(j)$ is the position of $j$ in the permutation. Then
$$ b_j=#{,k>j\mid P(k)<P(j),}, $$
because every inversion having second component $j$ consists of a larger element $k>j$ occurring to the left of $j$. Thus the problem is to determine, for each $j$, how many of the positions $P(j+1),P(j+2),\ldots,P(n)$ are less than $P(j)$.
A balanced binary search tree may be used for this purpose. Process the values $j=n,n-1,\ldots,1$. When $j$ is reached, the tree contains exactly the positions $P(j+1),\ldots,P(n)$. Insert $P(j)$ into the tree, maintaining at each node the size of its subtree. During the insertion, count how many stored positions are less than $P(j)$; this count is $b_j$. Since each insertion and rank computation requires time proportional to the height of the tree, and the height is proportional to $\log n$ on typical computers, each $b_j$ is obtained in time proportional to $\log n$. Repeating this for all $n$ values of $j$ yields the inversion table $b_1b_2\ldots b_n$ in time essentially proportional to $n\log n$.