Cортировка слиянием с использованием O(1) дополнительной памяти
Научившись сливать с использованием дополнительной памяти и операций , оставшееся решение задачи становится очевидным. Будем сливать не рекурсивно, чтобы сэкономить память в стеке. Пусть на i-том шаге у нас отсортированы подряд идущие, не пересекающиеся куски массива размером (за исключением последнего, его размер может быть меньше). Тогда сольем сначала первый и второй кусок, потом третий и четвертый и так до последнего. Если последнему куску нету пары, то просто ничего не делаем. Выполняем это для всех i от 2 до
Содержание
Алгоритм слияние
На вход алгоритм получает массив который состоит из двух отсортированных кусков. На выходе алгоритм возвращает отсортированный массив. Он состоит из нескольких шагов.
Шаг 1
Разобьем наш массив на группы подряд идущих элементов длиной . Остаток трогать не будем. Найдем группу содержащую конец первого отсортированного куска. Поменяем ее с последней. Добавим последнюю группу в остаток.
Количество операций на этом шаге .
Шаг 2
Возьмем и отсортируем группы по первому элементу(в случае равенства по последнему). Это можно сделать любой квадратичной или более быстрой сортировкой, которая требует дополнительной памяти , например сортировка выбором. Следует заметить что после сортировки этих групп элементы которые стоять левее заданного и больше его, находились в противоположном куске отсортированного массива, также они находятся в пределах одной группы, поэтому количество инверсий для каждого элемента не больше .
Так как кусков количество операций на этом шаге .
Шаг 3
Попытаемся слить первую и вторую группу. Поменяем местами первую группу и часть остатка. И как в обычном слиянии пользуясь двумя указателями сливаем вторую группу и только что измененную часть остатка. Результат начинаем записывать с начала первой группы. Чтобы ничего не перетерлось вместо записи используем обмен элементов. Так как группы имеют одинаковую длину и между указателем на вторую группу и указателем на запись расстояние равно длине группы, то слияние произойдет корректно.
Пример : Пусть длины групп = 3 и x1<y1<x2<x3<y3, где первая группа x1,x2,x3 , а вторая y1,y2,y3.
| Номер операции | Массив до выполнения операции | Массив после выполнения операции |
|---|---|---|
| 1 | [x1,x2,x3,y1,y2,y3,a1,a2,a3] | [a1,a2,a3,y1,y2,y3,x1,x2,x3] |
| 2 | [a1,a2,a3,y1,y2,y3,x1,x2,x3] | [x1,a2,a3,y1,y2,y3,a1,x2,x3] |
| 3 | [x1,a2,a3,y1,y2,y3,a1,x2,x3] | [x1,y1,a3,a2,y2,y3,a1,x2,x3] |
| 4 | [x1,y1,a3,a2,y2,y3,a1,x2,x3] | [x1,y1,x2,a2,y2,y3,a1,a3,x3] |
| 5 | [x1,y1,x2,a2,y2,y3,a1,a3,x3] | [x1,y1,x2,y2,a2,y3,a1,a3,x3] |
| 6 | [x1,y1,x2,y2,a2,y3,a1,a3,x3] | [x1,y1,x2,y2,x3,y3,a1,a3,a2] |
Потом, аналогично сольем вторую и третью группу и так до последней группы. Так как после второго шага количество инверсий для каждого элемента не больше то ему надо сдвинутся влево не больше чем на элементов, поэтому в конце не учитывая остаток массив будет отсортированный.
Количество групп и каждое слияние работает за , поэтому количество операций на этом шаге .
Шаг 4
Пусть размер остатка s. Начиная с конца разобьем наш массив на подряд идущие группы длиной s. Используя квадратичную или более быструю сортировку, которая требует дополнительной памяти отсортируем подмассив длиной 2s, который находится в конце. На последних s местах будут находится s максимальных элементов. Оставшаяся часть представляет собой массив содержащий две отсортированные части, причем размер второй равен s. По аналогии с шагом 3 сливаем задом на перед группы длиной s.
Количество операций на этом шаге .
Шаг 5
Опять используя экономную по памяти, хотя и квадратичную сортировку отсортируем:
1. остаток и первую группу.
2.последнюю группу.
Не стоит забывать что после новой разметки остаток находится в начале, а не в конце.
В результате массив будет отсортированным
Количество операций на этом шаге .
