Алгоритм сортировки слиянием

Сортировка слиянием (merge sort) — один из самых популярных алгоритмов сортировки, который помогает освоить навыки составления рекурсивных алгоритмов.

Стратегия «разделяй и властвуй»

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

Предположим, нужно отсортировать массив A. Подзадачей будет сортировка подраздела этого массива, начиная с индекса p и заканчивая индексом r, обозначенного как A[p..r].

«Разделяй»

Если q — это точка на полпути между p и r, то подмассив A [p.. r] можно разделить на два массива: A [p.. q] и A [q + 1, r].

«Властвуй»

На этапе «властвуй» сортируем оба подмассива A[p..q] и A[q+1, r]. Если мы еще не достигли базового случая, снова разделяем эти подмассивы и сортируем.

Объединение

Если этап «завоевания» достигает базового, и для массива A[p..r] мы получаем два отсортированных подмассива A[p..q] и A[q+1, r], объединяем их результаты, создавая отсортированный массив A[p..r] из двух отсортированных A[p..q] и A[q+1, r]

Алгоритм MergeSort

В merge sort алгоритме одноименная функция делит массив на две половины пока не будет достигнут этап, где p == r.

После этого начинает действовать функция слияния. Она соединяет отсортированные массивы в более крупные пока не будет объединен весь массив.

MergeSort(A, p, r)
    If p > r 
        return;
    q = (p+r)/2;
    mergeSort(A, p, q)
    mergeSort(A, q+1, r)
    merge(A, p, q, r)

Чтобы отсортировать весь массив, нужно вызвать MergeSort(A, 0, length(A)-1).

Алгоритм MergeSort

Как показано на рисунке, алгоритм сортировки слиянием рекурсивно делит массив пополам пока не будет достигнут базовый случай. Затем функция слияния собирает отсортированные подмассивы и объединяет их, чтобы отсортировать весь массив.

Алгоритм MergeSort - 2

Этап слияния

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

Алгоритм merge sort C поддерживает три указателя: по одному для каждого из двух массивов, и один для текущего индекса окончательного отсортированного массива.

Этап слияния
Этап слияния - 2

Поскольку во втором массиве больше не осталось элементов, и известно, что оба массива были отсортированы при запуске, можно скопировать оставшиеся элементы из первого массива.

Написание кода для алгоритма слияния

Заметное различие между этапом слияния, описанным выше, и тем, который используется для merge sort, состоит в том, что функция слияния выполняется только для последовательных подмассивов. Вот почему нужен только массив, первая позиция, последний индекс первого подмассива (можно вычислить первый индекс второго подмассива) и последний индекс второго подмассива.

Наша задача состоит в объединении двух подмассивов A[p..q] и A[q+1..r], чтобы создать отсортированный массив A[p..r]. Таким образом, входными данными функции являются A, p, q и r.

Функция слияния работает следующим образом:

  1. Создает копии подмассивов L <- A[p..q] и M <- A[q+1..r].
  2. Создает три указателя i, j и k:
  • i сохраняет текущий индекс L, начиная с 1;
  • j сохраняет текущий индекс M, начиная с 1;
  • k сохраняет текущий индекс A[p..q], начиная с p.
  1. Пока не будет достигнут конец L или M, выбираем те, что больше среди элементов из L и M и помещаем их в нужной позиции в A[p..q]
  2. Когда заканчиваются элементы в L или M, выбираем оставшиеся элементы и помещаем в A[p..q]

В коде реализации merge sort алгоритма это будет выглядеть следующим образом:

void merge(int A[], int p, int q, int r)
{
    /* Создать L <- A[p..q] and M <- A[q+1..r] */
    int n1 = q - p + 1;
    int n2 =  r - q;
 
    int L[n1], M[n2];

    for (i = 0; i < n1; i++)
        L[i] = A[p + i];
    for (j = 0; j < n2; j++)
        M[j] = A[q + 1 + j];
    
    /* Сохранить текущий индекс подмассивов и основной массив */
    int i, j, k;
    i = 0; 
    j = 0; 
    k = p; 


    /*Пока не будет достигнут конец L или M, выбираем те, что больше среди элементов из L и M, и помещаем их в нужной позиции в A[p..r] */
    while (i < n1 && j < n2)
    {
        if (L[i] <= M[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = M[j];
            j++;
        }
        k++;
    }
 
    /* Когда заканчиваются элементы в L или M, выбираем оставшиеся элементы и помещаем в A[p..r] */
    while (i < n1)
    {
        A[k] = L[i];
        i++;
        k++;
    }
 
    while (j < n2)
    {
        A[k] = M[j];
        j++;
        k++;
    }
}

Пошаговое пояснение функции слияния

Рассмотрим пример merge sort, который покажет, как это все работает:

Пошаговое пояснение функции слияния

Массив A[0..8] содержит два отсортированных подмассива A[1..5] и A[6..7]. Рассмотрим, как функция слияния объединяет два массива.

void merge(int A[], int p = 1, int q = 4, int 6)
{

Шаг 1: Создать повторяющиеся копии подмассивов для сортировки

/* Создать L <- A[p..q] and M <- A[q+1..r] */
    n1 = 4 - 1 + 1 = 4;
    n2 =  6 - 4 = 2;
 
    int L[4], M[2];

    for (i = 0; i < 4; i++)
        L[i] = A[p + i];
    /* L[0,1,2,3] = A[1,2,3,4] = [1,5,10,12] */

    for (j = 0; j < 2; j++)
        M[j] = A[q + 1 + j];
    /* M[0,1,2,3] = A[5,6] = [6,9]

Шаг 2: Сохранить текущий индекс подмассивов и основной массив merge sort C

int i, j, k;
    i = 0; 
    j = 0; 
    k = p;

Шаг 3: Пока не будет достигнут конец L или M, выбираем те, что больше среди элементов из L и M, и помещаем их в нужной позиции в A[p..r]

while (i < n1 && j < n2) { 
        if (L[i] <= M[j]) { 
            A[k] = L[i]; i++; 
        } 
        else { 
            A[k] = M[j]; 
            j++; 
        } 
        k++; 
    }

Шаг 4: Когда заканчиваются элементы в L или M, выбираем оставшиеся элементы и помещаем в A[p..r]

/* Выходим из предыдущего цикла, поскольку i < n1 не поддерживается */  
    while (i < n1)
    {
        A[k] = L[i];
        i++;
        k++;
    }
Шаг 4: Когда заканчиваются элементы в L или M, выбираем оставшиеся элементы и помещаем в A[p..r] - 2
/* Выходим из предыдущего цикла, поскольку i < n1 не поддерживается */  
    while (i < n1)
    {
        A[k] = L[i];
        i++;
        k++;
    }

В примере merge sort алгоритма этот шаг необходим, если размер M был больше L. В конце функции слияния подмассив A[p..r] является отсортированным.

СМСергей Марочканичавтор статьи «Merge Sort Algorithm»