Изменения
→Алгоритм построения за O(N): position -> pos, BUCKET -> bucket
'''list<list<int>>''' bank(bucket)
'''for''' i = 0 to permutation.size
'''int''' position pos = (permutation[i] - 1)/(max / bucket) <font color=green>// Определяем в каком кармане должен лежать элемент</font>
'''int''' newPosition = 0
'''while''' newPosition < bank[pos].size '''and''' bank[pos][newPosition] < permutation[i] <font color=green>// идем до позиции где должен стоять элемент permutation[i] </font>
newPosition++
answer += bank[pos].size - newPosition <font color=green>// ищем сколько инверсий эленент создает в своем кармане</font>
bank[pos].insert( newPosition , permutation[i] ) <font color=green>// вставляем элемент в Карман на свою позицию </font> '''for''' i = position + 1 to BUCKET bucket - 1 <font color=green>// ищем сколько инверсий он создает с элементами в других карманах</font>
answer += bank[i].size
'''return''' answer
В разделе [[Карманная сортировка | карманная сортировка]] доказывается, что она работает за линейное время. Что касается подсчета инверсий, то в приведенной реализации происходит [[Карманная сортировка | карманная сортировка]] в online режиме и вся математическая часть подходит и под этот случай.
Следует отметить, что хотя подсчет с помощью [[Карманная сортировка | карманной сортировки]] выполняется за линейное время, но имеет очень большую константу поэтому подсчет инверсий рассматриваемый выше за <tex>O(nlog(n)\log n)</tex> работает быстрее .
== Алгоритм восстановления ==
