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

Материал из Википедии — свободной энциклопедии

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

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

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

Нетривиальным этапом является соединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем две стопки карт, лежащих рубашками вниз так, что в любой момент мы видим верхнюю карту в каждой из этих стопок. Пусть также, карты в каждой из этих стопок идут сверху вниз в неубывающем порядке. Как сделать из этих стопок одну? На каждом шаге мы берём меньшую из двух верхних карт и кладём её (рубашкой вверх) в результирующую стопку. Когда одна из оставшихся стопок становится пустой, мы добавляем все оставшиеся карты второй стопки к результирующей стопке.

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

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

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

[править] C++

/**
 * @brief         Сортировка элементов от l до r массива buf
 * @param[in/out] buf - сортируемый массив
 * @param[in]     l - левая граница. При певой итерации l = 0
 * @param[in]     r - правая граница. При первой итерации r = buf.size() - 1
 *
 * В результате сортируются все элементы массива buf от l до r включительно.
 */
template<typename Type>
void MergeSort(vector<Type>& buf, size_t l, size_t r)
{
  //! Условие выхода из рекурсии
  if(l >= r) return;
 
  size_t m = (l + r) / 2;
 
  //! Рекурсивная сортировка полученных массивов
  sort_method(buf, l, m);
  sort_method(buf, m+1, r);
  merge(buf, l, r, m);
}
 
/**
 * @brief Слияние элементов.
 * @param[in/out] buf - массив
 * @param[in]     l - левая граница. При певой итерации l = 0
 * @param[in]     r - правая граница. При первой итерации r = buf.size() - 1
 * @param[in]     m - граница подмассивов.
 *
 * Массив buf содержит два отсортированных подмассива:
 * - [l; m] - первый отсортированный подмассив.
 * - [m+1; r] - второй отсортированный подмассив.
 * В результате получаем отсортированный массив, полученный из двух подмассивов,
 * который сохраняется в buf[l; r].
 */
template<typename Type>
static void merge(vector<Type>& buf, size_t l, size_t r, size_t m)
{
  if(l >= r || m < l || m > r) return;
  if(r == l + 1 && buf[l] > buf[r])
  {
    swap(buf[l], buf[r]);
    return;
  }
 
  vector<Type> tmp(r - l + 1);
 
  for(size_t i = 0; i < r - l + 1; i++) tmp[i] = buf[l + i]; 
 
  for(size_t i = l, j = 0, k = m - l + 1; i <= r; i++)
  {
    if(j > m - l)      buf[i] = tmp[k++];
    else if(k > r - l) buf[i] = tmp[j++];
    else               buf[i] = (tmp[j] < tmp[k]) ? tmp[j++] : tmp[k++];
  }
}

[править] Литература

Ананий В. Левитин Глава 4. Метод декомпозиции: Сортировка слиянием // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 169-172. — ISBN 0-201-74395-7