# Complexity of the standardization

Let $(A, \leq)$ be a totally ordered alphabet.

The standardization ${\tt std}(u)$ of a word $u \in A^n$ is the unique permutation of $n$ elements having the same inversions as $u$ (recall that an inversion of a word $u$ of length $n$ is a pair $(i, j)$ such that $1 \leq i < j \leq n$ and $u_i > u_j$; since permutations are words with some constraints, this definition also works for permutations).

For instance, let $A$ be the alphabet $\{a_i : i \in \mathbb{N}\}$ where $a_i \leq a_j$ if and only if $i \leq j$ and $u := a_3a_1a_4a_2a_5a_7a_4a_2a_3$. Then, we have ${\tt std}(u) = 416289735$.

To compute ${\tt std}(u)$, an obvious and naive algorithm consists in scanning $u$ from left to right $n$ times and assigning during the $i$th run the letter $i$ to the smallest not yet considerer letter. Applying this to the above example, we obtain \begin{array} & & a_3 & a_1 & a_4 & a_2 & a_5 & a_7 & a_4 & a_2 & a_3 \\ & & 1 & & & & & & & \\ & & 1 & & 2 & & & & & \\ & & 1 & & 2 & & & & 3 & \\ & 4 & 1 & & 2 & & & & 3 & \\ & 4 & 1 & & 2 & & & & 3 & 5 \\ & 4 & 1 & 6 & 2 & & & & 3 & 5 \\ & 4 & 1 & 6 & 2 & & & 7 & 3 & 5 \\ & 4 & 1 & 6 & 2 & 8 & & 7 & 3 & 5 \\ & 4 & 1 & 6 & 2 & 8 & 9 & 7 & 3 & 5 \\ \end{array} showing, assuming that $\leq$ is computable in constant time complexity, that the time complexity of ${\tt std}$ is $\mathcal{O}(n^2)$.

We can do better by using any stable sorting algorithm. The question is what is the best time complexity to compute the standardization of a word ?

-
How do you define the inversion of a word $u$? It seems that any stable sorting algorithm will do. en.wikipedia.org/wiki/Sorting_algorithm#Stability – Yoshio Okamoto Feb 15 '13 at 23:51
I just have edited my question by extending the notion of inversion for words. – Samuele Giraudo Feb 16 '13 at 10:08
I agree that any stable sorting algorithm will work. – Jeffε Feb 16 '13 at 16:58
This question is equivalent to producing the permutation corresponding to the stably sorted version of a given sequence, and therefore it cannot be solved faster than stable sorting. – Tsuyoshi Ito Feb 16 '13 at 20:03