338
правок
Изменения
м
Нет описания правки
Отсортируем блоки по возрастанию по первому элементу (если первые элементы равны, тогда по последнему).
[[Файл:Merge_O(1)_3.5_4.png|525px527px]]
Для этого подойдет любая квадратичная или более быстрая сортировка, которая требует <tex> O (1) </tex> дополнительной памяти. Для сохранения линейной асимптотики надо использовать алгоритм, линейный по числу обменов, т.е. подходит [[Сортировка выбором|сортировка выбором]]. Так как блоков <tex> \sqrt{n} </tex>, то количество операций на этом шаге <tex> O(n) </tex>. [[Файл:Merge_O(1)_4.png|525px]]
Следует заметить, что, после сортировки этих блоков, элементы, которые стоят левее заданного и больше его, находились в противоположной части отсортированного массива, также они находятся в пределах одной группы, поэтому количество инверсий для каждого элемента не больше <tex>\sqrt{n}</tex>.
