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

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

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

Этап слияния

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

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

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

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

Заметное различие между этапом слияния, описанным выше, и тем, который используется для 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.

3. Пока не будет достигнут конец L или M, выбираем те, что больше среди элементов из L и M и помещаем их в нужной позиции в A[p..q]
4. Когда заканчиваются элементы в 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++;
    }

/* Выходим из предыдущего цикла, поскольку i < n1 не поддерживается */  
    while (i < n1)
    {
        A[k] = L[i];
        i++;
        k++;
    }

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