Return to Answer

TL;DR: There is a simple algorithm that runs in time $O(n \log n)$ and finds the inversion vector of a given array. Furthermore, there is a time lower bound of $ \Omega (n \log n) $ for any comparison-based algorithm for this problem, based on a reduction to the sorting problem. I have never read the paper Yuval Filmus referenced to in his answer, but from a brief reading it seems that the operations that the data structure permits are not exactly what you need in order to implement an algorithm for computing the inversion vector.

Edit: As D.W. mentioned, the $ Ω(nlogn) $ lower bound only holds for comparison-based algorithms. There exist sorting algorithms whose running time is $o(nlogn)$, by going outside the comparison-based model.

TL;DR: There is a simple algorithm that runs in time $O(n \log n)$ and finds the inversion vector of a given array. Furthermore, there is a time lower bound of $ \Omega (n \log n) $ for any comparison-based algorithm for this problem, based on a reduction to the sorting problem. I have never read the paper Yuval Filmus referenced to in his answer, but from a brief reading it seems that the operations that the data structure permits are not exactly what you need in order to implement an algorithm for computing the inversion vector.

Edit: As D.W. mentioned, the $ Ω(nlogn) $ lower bound only holds for comparison-based algorithms. There exist sorting algorithms whose running time is $o(nlogn)$, by going outside the comparison-based model.

TL;DR: There is a simple algorithm that runs in time $O(n \log n)$ and finds the inversion vector of a given array. Furthermore, to the extent of my knowledge, there is a time lower bound of $ \Omega (n \log n) $ that comes from a reduction to the sorting problem. I have never read the paper Yuval Filmus referenced to in his answer, but from a brief reading it seems that the operations that the data structure permits are not exactly what you need in order to implement an algorithm for computing the inversion vector.

TL;DR: There is a simple algorithm that runs in time $O(n \log n)$ and finds the inversion vector of a given array. Furthermore, there is a time lower bound of $ \Omega (n \log n) $ for any comparison-based algorithm for this problem, based on a reduction to the sorting problem. I have never read the paper Yuval Filmus referenced to in his answer, but from a brief reading it seems that the operations that the data structure permits are not exactly what you need in order to implement an algorithm for computing the inversion vector.

Suppose by negativity that there exists an algorithm $\mathcal A$ that, given an array of elements $X$ and its length $n$, returns their inversion vector $Y$ in time $o (n\log n)$. Given the assumed algorithm $\mathcal A$, we present a sorting algorithm.

Edit: As D.W. mentioned, the $ Ω(nlogn) $ lower bound only holds for comparison-based algorithms. There exist sorting algorithms whose running time is $o(nlogn)$, by going outside the comparison-based model.

Suppose by negativity that there exists an algorithm $\mathcal A$ that, given an array of elements $X$ and its length $n$, returns their inversion vector $Y$ in time $o (n\log n)$. Given the assumed algorithm $\mathcal A$, we present a sorting algorithm.