Изменения

$T[1..n] = 0$ $For$ $i = 1..n$ $For$ $j = 1..(i - 1)$ $if$ $P[j] > P[i]$ $T[P[i]] = T[P[i]] + 1$

Отсортируем элементы Получим из исходной перестановки, сохраняя индексы. Массив обратную и запишем её в массив $M$ будет содержать номер позиции каждого элемента в исходной перестановке. Также заведём массив $S$ длиной $n$, инициализированный нулями. После обработки $i$-го элемента будем вносить значение 1 в ячейку $S[M[i]]$. Обработку начинаем с последнего элемента и двигаемся к началу. Пусть, функция $Sum(i)$ возвращает значение суммы элементов массива $S$ от 1 до $i$. Тогда $i$-й элемент таблицы инверсий находится так:

 Данная формула даёт правильный ответ, так как $S[M[i]]$ содержит единицу только в том случае, если мы уже обработали элемент, стоящий в $M[i]$-й позиции. Так как обработка идёт от больших чисел к меньшим, $Sum(M[i])$ выдаст нужное нам количество чисел, больших $i$ и стоящих в перестановке левее него. Функция $Sum $ реализуется с помощью [[Дерево отрезков. Построение|дерева отрезков]]. Каждое изменение массива и обращение к функции $Sum$ влечёт за собой $log_2 n\log_2n$ операций. Таким образом получаем сложность алгоритма $O(n*log_2 n\log_2n)$

Для восстановления таблицы перестановки из таблицы инверсий создаем таблицу, которую будем расширять, по мере добавления в неё чисел. Добавляем в эту таблицу число $i $ (где $i $ от $n $ до 1) на позицию $k+1$, где $k $ - число в таблице инверсий на $i$-том месте. Данный алгоритм довольно прост в реализации, но без использования дополнительных структур данных, имеет сложность $O(n^2)$, т. к. для вставки элемента в определённую позицию, требуется порядка $n$ перестановок элементов.

Приведём алгоритм восстановления с использованием [[Сортировка слиянием|сортировки слиянием]], имеющий сложность $O(n*log_2 n\log_2n)$.

Пусть $\alpha$ и $\beta$ - цепочки упорядоченных пар целых неотрицательных чисел $[m_1, n_1]...\dots[m_k, n_k]$. Рассмотрим двоичную операцию $o\circ$, рекурсивно определенную на парах таких цепочек следующим образом: $([m, n]\alpha)o\circ([m', n']\beta)=\left\{\begin{aligned}[] [m,n](\alpha o \circ ([m'-m, n']\beta)), m \le m',\\ [m', n'](([m-m'-1, n]\alpha) o \circ \beta), m>m'.\\

Сопоставим каждому элементу таблицы инверсий его номер. Получится множество упорядоченных пар чисел $[m_1, n_1]...\dots[m_k, n_k]$, где $m_i$ {{---}} сам элемент, а $n_i$ {{---}} его номер. Разобьем Разобьём данные элементы на пары и произведём с ними операцию $o\circ$. Получим некоторое количество цепочек упорядоченных пар. Также разбиваем их на пары и производим операцию $o\circ$. Так действуем, пока не останется одна цепочка. Выписывая вторые элементы данных упорядоченных пар в том порядке, в каком они представлены в цепочке, получим первоначальную перестановку. Цепочка наподобие $[4, 4][1,3]$ представляет "_ _ _ _ 4 _ 3 _ $\infty$", где "_" означает пропуск. Операция $\alpha \circ \beta$ вставляет пропуски и заполнения из $\beta$ на место пропусков в $\alpha$

* $[4, 1, 6, 3, 2, 2, 1, 1, 1, 0]$ - таблица инверсий.

* $[4,1]o\circ[1,2], [6,3]o\circ[3,4], [2,5]o\circ[2,6], [1,7]o\circ[1,8], [1,9]o\circ[0,10]$

* $[1,2][2,1]o\circ[3,4][2,3], [2,5][0,6]o\circ[1,7][0,8], [0,10][0,9]$

* $[1,2][2,1][0,4][2,3]o\circ[1,7][0,5][0,6][0,8], [0,10][0,9]$

* $[1,2][0,7][0,5][0,1][0,4][0,6][0,8][0,3]o\circ[0,10][0,9]$

* $[0,10][0,2][0,7][0,5][0,1][0,4][0,6][0,8][0,3][0,9]$

* Д. Кнут - Искусство программирования, том 3.