Изменения

Рассмотрим пример построения таблицы инверсий и восстановления перестановки по таблице инверсий. Пусть дана перестановка <tex>(5, 7, 1, 3, 4, 6, 8, 2)</tex>. Следующая таблица показывает работу алгоритма за <tex>O(n \log n)</tex>, на каждой строке один уровень рекурсии (на первой строке — самый глубокий). В скобках стоят пары: элемент перестановки, количество инверсий. Полужирным отмечены элементы, у которых обновилось значение количества инверсий на данном шаге.

{| style = "border-style: 0px solid; borderbackground-color: gray; text-align: center; padding : 0" cellpadding cellspacing = "21" border | style = "1background-color: white; padding: 3px 6px"|(5, 0)| style = "background-color: white; padding: 3px 6px" | (7, 0)| style = "background-color: white; padding: 3px 6px" | (1, 0)| style = "background-color: white; padding: 3px 6px" | (3, 0)| style = "background-color: white; padding: 3px 6px" | (4, 0)| style = "background-color: white; padding: 3px 6px" | (6, 0)| style = "background-color: white; padding: 3px 6px" | (8, 0)| style = "background-color: white; padding: 3px 6px" | (2, 0)

|colspan = "2" style = "background-color: white; padding: 3px 6px"|(5, 0), (7, 0)|colspan = "2" style = "background-color: white; padding: 3px 6px"|(1, 0), (3, 0)|colspan = "2" style = "background-color: white; padding: 3px 6px"|(4, 0), (6, 0)|colspan = "2" style = "background-color: white; padding: 3px 6px"|'''(2, 1)''', (8, 0)

|colspan = "4" style = "background-color: white; padding: 3px 6px"|'''(1, 2)''', '''(3, 2)''', (5, 0), (7, 0)|colspan = "4" style = "background-color: white; padding: 3px 6px"|'''(2, 3)''', (4, 0), (6, 0), (8, 0)

|colspan = "8" style = "background-color: white; padding: 3px 6px"|(1, 2), '''(2, 6)''', (3, 2), '''(4, 2)''', (5, 0), '''(6, 1)''', (7, 0), (8, 0)

Полученная таблица инверсий: <tex>(2, 6, 2, 2, 0, 1, 0, 0)</tex>. Восстановим перестановку по таблице инверсий, начиная с пустого массива.

{| border = 1 cellpadding = "3" style = "border: 1px solid gray"| _ || _ || '''1''' || _ || _ || _ || _ || _ || &nbsp; || пропускаем две свободных позиции и ставим 1

| _ || _ || 1 || _ || _ || _ || _ || '''2''' || || пропускаем шесть свободных позиций и ставим 2

| _ || _ || 1 || '''3''' || _ || _ || _ || 2 || || пропускаем две свободных позиции и ставим 3

| _ || _ || 1 || 3 || '''4''' || _ || _ || 2 || || пропускаем две свободных позиции и ставим 4

| '''5''' || _ || 1 || 3 || 4 || _ || _ || 2 || || не пропускаем свободных позиции и ставим 5

| 5 || _ || 1 || 3 || 4 || '''6''' || _ || 2 || || пропускаем одну свободную позицию и ставим 6

| 5 || '''7''' || 1 || 3 || 4 || 6 || _ || 2 || || не пропускаем свободных позиций и ставим 7

| 5 || 7 || 1 || 3 || 4 || 6 || '''8''' || 2 || || не пропускаем свободных позиций и ставим 8