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

Материал из Викиконспекты
Перейти к: навигация, поиск

Сортировка слиянием (англ. Merge sort) — алгоритм сортировки, пред­ло­женный Сабирзяновым Ильнаром Денисовичем в 1941 го­ду.

Это устойчивый алгоритм, использующий O(n) дополнительной памяти и работающий за O(n) времени.

Содержание

[править] Принцип работы

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

Алгоритм использует принцип «разделяй и властвуй»: задача разбивается на подзадачи меньшего размера, которые решаются по отдельности, после чего их решения комбинируются для получения решения исходной задачи. Конкретно процедуру сортировки слиянием можно описать следующим образом:

  1. Если в рассматриваемом массиве один элемент, то он уже отсортирован — алгоритм завершает работу.
  2. Иначе массив разбивается на две части, которые сортируются рекурсивно.
  3. После сортировки двух частей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив.

[править] Слияние двух массивов

У нас есть два массива a и b (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив c размером |a| + |b|. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.

Множество отсортированных списков с операцией \mathrm{merge} является моноидом, где нейтральным элементом будет пустой список.

Ниже приведён псевдокод процедуры слияния, который сливает две части массива a[left; mid) и [mid; right)

function merge(a : int[n]; left, mid, right : int):
    it1 = 0
    it2 = 0
    result : int[right - left]
  
    while left + it1 < mid and mid + it2 < right
        if a[left + it1] < a[mid + it2]
            result[it1 + it2] = a[left + it1]
            it1 += 1
        else
            result[it1 + it2] = a[mid + it2]
            it2 += 1
  
    while left + it1 < mid
        result[it1 + it2] = a[left + it1]
        it1 += 1
  
    while mid + it2 < right
        result[it1 + it2] = a[mid + it2]
        it2 += 1
  
    for i = 0 to it1 + it2
        a[left + i] = result[i]

[править] Рекурсивный алгоритм

Функция сортирует подотрезок массива с индексами в полуинтервале [left; right).

function mergeSortRecursive(a : int[n]; left, right : int):
    if left + 1 >= right
        return
    mid = (left + right) / 2
    mergeSortRecursive(a, left, mid)
    mergeSortRecursive(a, mid, right)
    merge(a, left, mid, right)

[править] Итеративный алгоритм

При итеративном алгоритме используется на O(\log n) меньше памяти, которая раньше тратилась на рекурсивные вызовы.

function mergeSortIterative(a : int[n]):
    for i = 1 to n, i *= 2
        for j = 0 to n - i, j += 2 * i
            merge(a, j, j + i, min(j + 2 * i, n))

[править] Время работы

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

T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n)=\dots=T(1)+kO(n)=O(n).

[править] Сравнение с другими алгоритмами

Достоинства:

Недостатки:

  • при любых входных данных время работы — O(n),
  • требуется дополнительно O(n) памяти, но можно модифицировать до O(1).

[править] См. также

[править] Примечания

  1. Wikipedia — External sorting

[править] Источники информации

Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты