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

Подробный алгоритм сортировки

Для решения задачи сортировки эти три этапа выглядят так:

1. Сортируемый массив разбивается на две части примерно одинакового размера;
2. Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
3. Два упорядоченных массива половинного размера соединяются в один.

1.1. — 2.1. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).

3.1. Соединение двух упорядоченных массивов в один.
Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два уже отсортированных по возрастанию подмассива. Тогда:
3.2. Слияние двух подмассивов в третий результирующий массив.
На каждом шаге мы берём меньший из двух первых элементов подмассивов и записываем его в результирующий массив. Счетчики номеров элементов результирующего массива и подмассива из которого был взят элемент увеличиваем на 1.
3.3. «Прицепление» остатка.
Когда один из подмассивов закончился, мы добавляем все оставшиеся элементы второго подмассива в результирующий массив.

Пример сортировки на языке С

/*
 * Сортирует массив используя рекурсивную сортировку слиянием
 * up - указатель на массив который нужно сортировать
 * down - указатель на массив с, как минимум, таким же размером как у 'up', используется как буфер
 * left - левая граница массива, передайте 0 чтобы сортировать массив с начала
 * right - правая граница массива, передайте длину массива - 1 чтобы сортировать массив до последнего элемента
 * возвращает: указатель на отсортированный массив. Из за особенностей работы данной имплементации, отсортированная версия массива может оказаться либо в 'up' либо в 'down
 */
int* merge_sort(int *up, int *down, unsigned int left, unsigned int right)
{

        if (left == right)
        {
                down[left] = up[left];
                return down;
        }

        unsigned int middle = (unsigned int)((left + right) * 0.5);

        // разделяй и сортируй
        int *l_buff = merge_sort(up, down, left, middle);
        int *r_buff = merge_sort(up, down, middle + 1, right);

        // слияние двух отсортированных половин
        int *target = l_buff == up ? down : up;

        unsigned int width = right - left, l_cur = left, r_cur = middle + 1;
        for (unsigned int i = left; i <= right; i++)
        {
                if (l_cur <= middle && r_cur <= right)
                {
                        if (l_buff[l_cur] < r_buff[r_cur])
                        {
                                target[i] = l_buff[l_cur];
                                l_cur++;
                        }
                        else
                        {
                                target[i] = r_buff[r_cur];
                                r_cur++;
                        }
                }
                else if (l_cur <= middle)
                {
                        target[i] = l_buff[l_cur];
                        l_cur++;
                }
                else
                {
                        target[i] = r_buff[r_cur];
                        r_cur++;
                }
        }

        return target;
}

Псевдокод алгоритма слияния без «прицепления» остатка на C++-подобном языке:

L = *In1;
R = *In2;
if( L == R ) {
 *Out++ = L;
 In1++;
 *Out++ = R;
 In2++;
} else if(L < R) {
 *Out++ = L;
 In1++;
} else {
 *Out++ = R;
 In2++;
}

Алгоритм был изобретён Джоном фон Нейманом в 1945 году.^[1]

В приведённом алгоритме на C++-подобном языке используется проверка на равенство двух сравниваемых элементов подмассивов с отдельным блоком обработки в случае равенства. Отдельная проверка на равенство удваивает число сравнений, что замедляет алгоритм и усложняет код программы. Вместо отдельной проверки на равенство и отдельного блока обработки в случае равенства можно использовать одну общую проверку if(L <= R) и общий блок обработки во всех случаях, что вдвое уменьшает число проверок, повышает быстродействие программ, почти вдвое уменьшает код программы и упрощает алгоритм.

Псевдокод улучшенного алгоритма слияния без «прицепления» остатка на C++-подобном языке:

L = *In1;
R = *In2;

if( L <= R ) {
 *Out++ = L;
 In1++;
} else {
 *Out++ = R;
 In2++;
}

Две операции пересылки в переменные L и R упрощают некоторые записи в программе, что может оказаться полезным в учебных целях, но в действительных программах они потребляют дополнительное машинное время и дополнительные ячейки памяти, поэтому в действительных программах они не нужны и их можно удалить, что ещё более увеличит быстродействие, уменьшит расход памяти и сократит программный код.
Псевдокод ещё более улучшенного алгоритма слияния без «прицепления» остатка на C++-подобном языке:

if( *In1 <= *In2 ) {
 *Out++ = *In1;
 In1++;
} else {
 *Out++ = *In2;
 In2++;
}

Время работы алгоритма порядка O(n * log n) при отсутствии деградации на неудачных случаях, которая является больным местом быстрой сортировки (тоже алгоритм порядка O(n * log n), но только для среднего случая). Расход памяти выше, чем для быстрой сортировки, при намного более благоприятном паттерне выделения памяти — возможно выделение одного региона памяти с самого начала и отсутствие выделения при дальнейшем исполнении.

Популярная реализация требует однократно выделяемого временного буфера памяти, равного сортируемому массиву, и не имеет рекурсий. Шаги реализации:

1. InputArray = сортируемый массив, OutputArray = временный буфер
2. над каждым отрезком входного массива InputArray[N * MIN_CHUNK_SIZE..(N + 1) * MIN_CHUNK_SIZE] выполняется какой-то вспомогательный алгоритм сортировки, например, сортировка Шелла или быстрая сортировка.
3. устанавливается ChunkSize = MIN_CHUNK_SIZE
4. сливаются два отрезка InputArray[N * ChunkSize..(N + 1) * ChunkSize] и InputArray[(N + 1) * ChunkSize..(N + 2) * ChunkSize] попеременным шаганием слева и справа (см. выше), результат помещается в OutputArray[N * ChunkSize..(N + 2) * ChunkSize], и так для всех N, пока не будет достигнут конец массива.
5. ChunkSize удваивается
6. если ChunkSize стал >= размера массива — то конец, результат в OutputArray, который (ввиду перестановок, описанных ниже) есть либо сортируемый массив, либо временный буфер, во втором случае он целиком копируется в сортируемый массив.
7. иначе меняются местами InputArray и OutputArray перестановкой указателей, и все повторяется с пункта 4.

Такая реализация также поддерживает размещение сортируемого массива и временного буфера в дисковых файлах, то есть пригодна для сортировки огромных объемов данных. Реализация ORDER BY в СУБД MySQL при отсутствии подходящего индекса устроена именно так (источник: filesort.cc в исходном коде MySQL).

Пример реализации алгоритма простого двухпутевого слияния на псевдокоде:

function mergesort(m)
    var list left, right, result
    if length(m) ≤ 1
        return m
    else
        middle = length(m) / 2
        for each x in m up to middle
            add x to left
        for each x in m after middle
            add x to right
        left = mergesort(left)
        right = mergesort(right)
        result = merge(left, right)
        return result
    end if

Есть несколько вариантов функции merge(), наиболее простой вариант может выглядеть так:

function merge(left,right)
    var list result
    while length(left) > 0 and length(right) > 0
        if first(left) ≤ first(right)
            append first(left) to result
            left = rest(left)
        else
            append first(right) to result
            right = rest(right)
        end if
    if length(left) > 0 
        append left to result
    if length(right) > 0 
        append right to result
    return result

Примечания

Литература

• Ананий В. Левитин. Глава 4. Метод декомпозиции: Сортировка слиянием // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 169-172. — ISBN 5-8459-0987-2.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.

Достоинства и недостатки

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

• Работает даже на структурах данных последовательного доступа.
• Хорошо сочетается с подкачкой и кэшированием памяти.
• Неплохо работает в параллельном варианте: легко разбить задачи между процессорами поровну, но трудно сделать, что если один процессор задержится, остальные возьмут его работу на себя.
• Не имеет «трудных» входных данных.

Недостатки:

• На «почти отсортированных» массивах работает столь же долго, как на хаотичных.
• Требует дополнительной памяти по размеру исходного массива.

Ссылки

• Многофазное слияние на algolist.manual.ru
• Сортировка слиянием — восходящая сортировка, естественная сортировка, измерение быстродействия.
• Описание метода и листинг программ сортировки слиянием.