Знак перестановки: транспозиции vs инверсии

[wataru]

Наконец отметим, что подсчёт инверсий требует время O(n^2): их наибольшее число равно

Вообще-то, нет. Есть куча методов за O(n log n). Самый распиаренный — отсортировать перестановку как массив алгоритмом слияния. Во время слияния двух списков можно считать инверсии: если берем элемент из правого списка, то прибавляем к ответу, сколько там осталось в левом списке.

Другой вариант — через структуры данных. Один раз пройтись по массиву и в каком-нибудь BST складывать все встреченные числа и считать, сколько там чисел больше текущего (за логарифм). Еще для этого можно использовать дерево Фенвика или дерево отрезков.