Сортировка слиянием
Описание
Сортировка слиянием — алгоритм сортировки. Он был предложен Джоном фон Нейманом в 1945 году.
Это стабильный алгоритм, использующий дополнительной памяти и времени.
Принцип работы
Этот алгоритм использует принцип «разделяй и властвуй». Этот принцип заключается в том, что исходная задача разбивается на подзадачи меньшего размера, а потом они решаются рекурсивным методом или же конкретно, если их размер мал. Потом из решения объединяются и получается решение основной (исходной) задачи.
Для процедуры слияния требуется два отсортированных массива. Зная, что массив из одного элемента по определению отсортирован, мы можем разработать такой алгоритм:
- Массив разбивается на половинки до тех пор, пока размер "половинки" не станет равным единице.
- Каждая из получившихся частей сортируется отдельно. Или же это просто одиночный элемент.
- "Сливаем" два упорядоченных массива в один.
Слияние двух массивов
У нас есть два массива и . Нам надо получить массив размером . Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
Алгоритм слияния формально можно записать следующим образом:
// слияние двух массивов с помощью временного
merge(array a, int left, int middle, int right) // left - левая граница, right - правая, middle - середина
array b = a[middle + 1, right];
i = left, j = middle + 1, k = 0;
array temp = new array[sizeof(a) + sizeof(b)];
while i <= middle and j <= right
temp[k++] = (a[j] < b[i]) ? a[j++] : b[i++];
while i <= middle
temp[k++] = b[i++];
while j <= right
temp[k++] = a[j++];
for (int t = 0; t != k; t++)
a[t] = temp[t];
// в конце a[1..k] это будет отсортированный массив
Рекурсивный алгоритм
Функция сортирует участок массива от элемента с номером left до элемента с номером right:
right и left — правая и левая граница массива, middle — середина.
Условие выхода — если массив стал состоять из 1 элемента.
sort(array a, int left, int right)
middle = (left + right) / 2;
if middle == right
return;
sort(a, left, middle);
sort (a, middle, right);
merge(array a, left, middle, right);
Пример работы алгоритма показан на рисунке:
Восходящая сортировка слиянием
Помимо рекурсивного алгоритма существует и альтернативный. Пример работы алгоритма показан на рисунке:
- Выделим память размером с занимаемой памяти исходного массива.
- Попарно сравним элементы, записывая во временную память.
- Поменяем указатели временного и исходного массива.
- Выполним слияние "кусочков" размером два.
- Повторяем до тех пор, пока не сделаем единый кусок.
Процедуру слияния надо будет изменить, так, что-бы она записывала результат в результирующий массив (mas1)
sort(array mas, int elementsAmount)
array mas1 = new array[elementsAmount];
for(int size = 1; size < elementsAmount; size *= 2)
int start = 0;
while ((start + size) < elementsAmount)
merge(mas /*наш массив*/, mas + start /*левая граница*/,
mas + start + size /*середина*/,
mas + start + size + min(size, elementsAmount - start - size)) /*правая граница*/;
start += size * 2;
while (start < elementsAmount)
mas1[start] = mas[start];
++start;
array temp = mas1;
mas1 = mas;
mas = temp;
Время работы
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай — время сортировки массива длины n, тогда для сортировки слиянием справедливо
( — это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:
Осталось оценить . Мы знаем, что , а значит . Уравнение примет вид . Так как — константа, то .
