Сортировка слиянием

Описание

Действие алгоритма.

Сортировка слиянием — алгоритм сортировки. Он был пред­ло­жен Джо­ном фон Ней­ма­ном в 1945 го­ду.

Это ста­биль­ный ал­го­ритм, использующий [math]O(n)[/math] дополнительной памяти и [math]O(n[/math] [math]\log(n))[/math] времени.

Принцип работы

Этот алгоритм хороший пример использования принципа «разделяй и властвуй» — сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Для процедуры слияния требуется два отсортированных массива. Зная, что массив из одного элемента по определению отсортирован, мы можем разработать такой алгоритм:

1. Массив разбивается на половинки до тех пор, пока размер "половинки" не станет равным единице.
2. Каждая из получившихся частей сортируется отдельно. Или же это просто одиночный элемент.
3. "Сливаем" два упорядоченных массива в один.

Слияние двух массивов

Допустим, у нас есть два отсортированных массива А и B размерами [math]N_a [/math] и [math]N_b [/math] со­ответственно, и мы хотим объединить их элементы в один большой отсортирован­ный массив C размером [math]N_a + N_b [/math] . Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.

Пример работы процедуры слияния.

Алгоритм слияния формально можно записать следующим образом:

// слияние двух массивов с помощью временного
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)

Пример работы алгоритма показан на рисунке:

Восходящая сортировка слиянием

Пример работы восходящей сортировки слиянием

Помимо рекурсивного алгоритма существует и альтернативный. Пример работы алгоритма показан на рисунке:

1. Выделим память размером с занимаемой памяти исходного массива.
2. Попарно сравним элементы, записывая во временную память.
3. Поменяем указатели временного и исходного массива.
4. Выполним слияние "кусочков" размером два.
5. Повторяем до тех пор, пока не сделаем единый кусок.
6. Удаляем временный массив.

Процедуру слияния надо будет изменить, так, что-бы она записывала результат в результирующий массив (mas1)

sort(array * mas, int elementsAmount)
  array * mas1 =  new array[elementsAmount];
  for(int size = 1; size < elementsAmount; size *= 2) {
    int start = 0; 
    for(; (start + size) < elementsAmount; start += size * 2) 
      merge(mas + start, mas + start,
          mas + start + size, 
          mas + start + size + min(size,elementsAmount - start - size));
    for(; start < elementsAmount; ++start)
      mas1[start] = mas[start];
    array * temp = mas1;
    mas1 = mas;
    mas = temp; 
  delete[] mas1;

Время работы

Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай [math]T(n)[/math] — время сортировки массива длины n, тогда для сортировки слиянием справедливо [math]T(n)=2T(n/2)+O(n)[/math]
([math]O(n)[/math] — это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:

[math]T(n)[/math] [math]=[/math] [math]2T(n/2)[/math] [math]+[/math] [math]O(n)[/math] [math]=[/math] [math]4T(n/4)[/math] [math]+[/math] [math]2*O(n)[/math] [math]=[/math] [math]...[/math] [math]=[/math] [math]2^kT(1)[/math] [math]+[/math] [math]kO(n).[/math]

Осталось оценить [math]k[/math]. Мы знаем, что [math]2^k=n[/math], а значит [math]k=\log(n)[/math]. Уравнение примет вид [math]T(n)=nT(1)+ \log(n)O(n)[/math]. Так как [math]T(1)[/math] — константа, то [math]T(n)=O(n)+\log(n)O(n)=O(n\log(n))[/math].

Ссылки

• Википедия — сортировка слиянием
• Сортировка слиянием, анимация и свойства (англ.)
• Примеры реализации на различных языках (Википедия)
• Сортировка слиянием в картинках (источник картинок в статье)