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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Сортировка слиянием
Merge-sort-example-300px.gif
Пример сортировки слиянием. Сначала делим список на кусочки (по 1 элементу), затем сравниваем каждый элемент с соседним, сортируем и объединяем. В итоге, все элементы отсортированы и объединены вместе.
Предназначение

Алгоритм сортировки

Структура данных

Массив

Худшее время

O(n log n)

Лучшее время

O(n log n) обычно, O(n) на упорядоченном массиве

Среднее время

O(n log n)

Затраты памяти

O(n) вспомогательных

Сортировка слиянием (англ. 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++11:

#include <algorithm>
#include <cstddef>
#include <iterator>
 
template<typename T>
void merge_sort(T array[], std::size_t size) noexcept
{
    if (size > 1)
    {
        std::size_t const left_size = size / 2;
        std::size_t const right_size = size - left_size;
 
        merge_sort(&array[0], left_size);
        merge_sort(&array[left_size], right_size);
 
        std::size_t lidx = 0, ridx = left_size, idx = 0;
        T *tmp_array = new T[size];
 
        while (lidx < left_size || ridx < size)
        {
            if (array[lidx] < array[ridx])
            {
                tmp_array[idx++] = std::move(array[lidx]);
                lidx++;
            }
            else
            {
                tmp_array[idx++] = std::move(array[ridx]);
                ridx++;
            }
 
            if (lidx == left_size)
            {
                std::copy(std::make_move_iterator(&array[ridx]),
                          std::make_move_iterator(&array[size]),
                          &tmp_array[idx]);
                break;
            }
            if (ridx == size)
            {
                std::copy(std::make_move_iterator(&array[lidx]),
                          std::make_move_iterator(&array[left_size]),
                          &tmp_array[idx]);
                break;
            }
        }
 
        std::copy(std::make_move_iterator(tmp_array),
                  std::make_move_iterator(&tmp_array[size]),
                  array);
 
        delete []tmp_array;
    }
}

Псевдокод алгоритма слияния без «прицепления» остатка на 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

Примечания[править | править вики-текст]

  1. Knuth D.E. The Art of Computer Programming. Volume 3: Sorting and Searching. — 2nd. — Addison-Wesley, 1998. — P. 159. — ISBN 0-201-89685-0.

Литература[править | править вики-текст]

  • Ананий В. Левитин. Глава 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.

Достоинства и недостатки[править | править вики-текст]

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

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

Недостатки:

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

Ссылки[править | править вики-текст]