1
правка
Изменения
м
→Алгоритм построения за O(N log N)
Пусть дано разбиение перестановки на два списка, причём для каждого элемента дано число инверсий слева с элементами того же списка и известно, что все числа первого списка стоят левее всех чисел второго списка в исходной перестановке. Будем считать количество инверсий слева элементов обоих списков следующим образом: сливаем списки, аналогично [[Сортировка_слиянием |сортировке слиянием.]]
Если в результат нужно записать элемент первого списка, то все нерассмотренные элементы второго списка больше, следовательно, количество инверсий для этого элемента не меняется. Если в результат нужно записать элемент второго списка, то все нерассмотренные элементы первого списка больше его и стоят левее. Следовательно, количество инверсий для этого элемента следует увеличить на количество нерассмотренных элементов второго первого списка.
Описанный алгоритм записывается в псевдокод следующим образом:
