Merge Sort Algorithm

алгоритм, сортировка слиянием, Merge Sort Algorithm, сортировка

Merge sort is a kind of divide and conquer algorithm in computer programming. It is one of the most popular sorting algorithms and a great way to build confidence in building recursive algorithms.

Divide and Conquer Strategy

Using the Divide and Conquer technique, we divide the problem into subtasks. When the solution for each subproblem is ready, we "combine" the results from the subproblems to solve the main problem.

Suppose we needed to sort an array A. The subtask would be to sort a subsection of this array starting at index p and ending at index r, denoted as A[p..r].

Share

If q is an intermediate point between p and r, then we can split the subarray A[p..r] into two arrays A[p..q] and A[q + 1, r].

Own it

In the conquest step, we are trying to sort both subarrays A[p..q] and A[q + 1, r]. If we haven't reached the base case yet, we separate both of these subarrays again and try to sort them.

Combine

When the conqueror step reaches the base step and we get two sorted subarrays A[p..q] and A[q + 1, r] for array A[p..r], we combine the results, creating a sorted array A[p. .r] of two sorted subarrays A[p..q] and A[q + 1, r]

Merge sort algorithm

The MergeSort function repeatedly divides the array into two halves until we reach a stage where we try to MergeSort on a subarray of size 1, i.e. p == r.
After that, the merge function comes into play, which merges the sorted arrays into larger arrays until the entire array has been merged.

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)

To sort the entire array, we need to call MergeSort(A, 0, length(A)-1).
As shown in the figure below, the merge sort algorithm recursively divides the array into two halves until we reach the base case of an array with 1 element. The merge function then selects the sorted subarrays and merges them to gradually sort the entire array.

Merge sort merge step

Each recursive algorithm depends on a base case and the ability to combine results from base cases. merge sort is no exception. The most important part of the algorithm is the "merge" step.

The merge step is a solution to the simple problem of combining two sorted lists (arrays) to create one large sorted list (array).

The algorithm maintains three pointers, one for each of the two arrays and one for maintaining the current index of the final sorted array.

Достигли ли мы конца какого-либо из массивов?
    Нет:
        Сравните текущие элементы обоих массивов
        Скопируйте меньший элемент в отсортированный массив
        Переместить указатель на элемент, содержащий меньший элемент
    Да:
        Скопировать все оставшиеся элементы непустого массива

Since there are no more elements left in the second array and we know that both arrays were sorted at startup, we can copy the remaining elements from the first array directly

Writing code for the merge algorithm

A notable difference between the merge step we described above and the one we use for merge sort is that the merge function is only performed on consecutive subarrays.

That's why we only need the array, the first position, the last index of the first subarray (we can compute the first index of the second subarray), and the last index of the second subarray.

Our task is to combine two subarrays A[p..q] and A[q + 1..r] to create a sorted array A[p..r]. Thus, the input data for the function A, p, q and r

The merge function works like this:

1. Create copies of the subarrays L ← A [p..q] and M ← A [q + 1..r].
2. Create three pointers i, j and k
3. i maintains the current index L starting from 1
4. j maintains the current index of M, starting at 1
5. k maintains the current index of A [p..q] starting from p
6. Until we reach the end of L or M, choose the larger of the elements from L and M and place them in the correct position in A[p..q]
7. When we run out of elements in L or M, take the remaining elements and put in A [p..q]

In code it will look like this:

void merge(int A[], int p, int q, int r)
{
    /* Создание L ← A[p..q] и 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 function step by step

There is a lot of action in this function, so let's take a look at an example to see how it would work.

The array A[0..8] contains two sorted subarrays A[1..5] and A[6..7]. Let's see how the merge function will merge two arrays.

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

Step 1. Create duplicate copies of subarrays for sorting

 /* Создание L ← A[p..q] и 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]

Step 2: Maintaining the current index of the sub-arrays and the main array

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

Step 3: Until we reach the end of L or M, the larger one among the L and M elements is selected and placed in the correct position at point 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++; 
    }

Step 4: When the elements in L or M run out, the remaining elements must be placed in A [p..r]

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

/* Мы вышли из предыдущего цикла, потому что i <n1 не выполняется */  

    while (j < n2)
    {
        A[k] = M[j];
        j++;
        k++;
    }
}

This step would be necessary if the size M was larger than L.
At the end of the merge function, the subarray A[p..r] is sorted.