Сортировка слиянием
Описание
Сортировка слиянием — алгоритм сортировки. Он был предложен Джоном фон Нейманом в 1945 году.
Это стабильный алгоритм, использующий дополнительной памяти и времени.
Принцип работы
Этот алгоритм использует принцип «разделяй и властвуй» — сначала задача разбивается на несколько подзадач меньшего размера, затем эти задачи решаются с помощью рекурсивного вызова или, если они малы, то уже конкретно. Потом их решения комбинируются, и получается решение исходной задачи.
Для процедуры слияния требуется два отсортированных массива. Зная, что массив из одного элемента по определению отсортирован, мы можем разработать такой алгоритм:
- Массив разбивается на половинки до тех пор, пока размер "половинки" не станет равным единице.
- Каждая из получившихся частей сортируется отдельно. Или же это просто одиночный элемент.
- "Сливаем" два упорядоченных массива в один.
Слияние двух массивов
Допустим, у нас есть два отсортированных массива А и B размерами и соответственно, и мы хотим объединить их элементы в один большой отсортированный массив C размером . Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
Алгоритм слияния формально можно записать следующим образом:
// слияние двух массивов с помощью временного
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;
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 = right / 2
if middle == right
return
sort(a, left, middle)
sort (a, middle + 1, 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 + start, 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, тогда для сортировки слиянием справедливо
( — это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:
Осталось оценить . Мы знаем, что , а значит . Уравнение примет вид . Так как — константа, то .
