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

Сор­ти­ров­ка слия­ни­ем — относится к быстрым алгоритмам сортировки и является пожалуй одним из самых простых из этого списка. Осо­бен­но­стью это­го ал­го­рит­ма яв­ля­ет­ся то, что он ра­бо­та­ет с эле­мен­та­ми мас­си­ва пре­иму­ще­ствен­но по­сле­до­ва­тель­но. Кро­ме то­го, сор­ти­ров­ка слия­ни­ем — чуть ли не един­ствен­ный ал­го­ритм, ко­то­рый мо­жет быть эф­фек­тив­но ис­поль­зо­ван для сор­ти­ров­ки та­ких ст­рук­тур дан­ных, как свя­зан­ные спис­ки. По­сле­до­ва­тель­ная ра­бо­та с эле­мен­та­ми мас­си­ва зна­чи­тель­но уве­ли­чи­ва­ет ско­рость сор­ти­ров­ки в си­сте­мах с кэ­ши­ро­ва­ни­ем.

Сор­ти­ров­ка слия­ни­ем — ста­биль­ный ал­го­ритм сор­ти­ров­ки. Это озна­ча­ет, что по­ря­док «рав­ных» эле­мен­тов не из­ме­ня­ет­ся в ре­зуль­та­те ра­бо­ты ал­го­рит­ма. В не­ко­то­рых за­да­чах это свой­ство до­ста­точ­но важ­но.

Этот ал­го­ритм был пред­ло­жен Джо­ном фон Ней­ма­ном в 1945 го­ду.

Алгоритм

Подобно QuickSort, Merge Sort является алгоритмом класса "Разделяй и властвуй". Он делит входной массив на две половины, вызывается рекурсивно от каждой из получившихся половин, а затем объединяет две отсортированные половины. Функцию merge() будем использовать для слияния двух половин. merge(arr, l, m, r) является ключевым процессом, предполагающим, что arr [l..m] и arr [m + 1..r] сортируются и объединяют два отсортированных подмассива в один. Нагляднее на изображении.

Каждая итерация сортировки представима тремя шагами:

1)Сортируемый массив разбивается на две части примерно одинакового размера;

2)Каждая из получившихся частей сортируется.

3)Два упорядоченных массива половинного размера соединяются в один.

Рекурсивные вызовы происходят до тех пор, пока длина массива не равна 1, потому как массив длиной 1 является отсортированным. Так как мы будем пользоваться переменными r и l, которые будут указывать на правый и левый элементы соотвественно, проверить выполнение вышеописанного условия можно простым сравнением if(r>l).

После достижения длины 1 рекурсия начинает "схлопываться", т.е. соединять уже отсортированные половинки.

Эту управляющую роль будет выполнять метод mergeSort()

void mergeSort(int arr[], int l, int r){
    if (l < r){

        int middle = l+(r-l)/2;    

        mergeSort(arr, l, middle);
        mergeSort(arr, middle+1, r);

        merge(arr, l, middle, r);
    }
}

Теперь поподробнее про метод merge(int arr[], int left, int middle, int right). Рассмотрим его тоже в виде последовательности шагов.

Введем два вспомогательных массива для двух половин входящего массива.

void merge(int arr[], int left, int middle, int right){
    sizeOfLeftPart = middle-left+1;
    sizeOfRightPart = right-middle;
    int leftPart[sizeOfLeftPart], int rightPart[sizeOfRightPart];
...

Скопируем элементы каждой их частей массива в созданные на предыдущем шаге вспомогательные массивы.

...
for (int i = 0; i < sizeOfLeftPart; i++)
    leftPart[i] = arr[left + i];
for (int i = 0; i < sizeOfRightPart; i++)
    rightPart[i] = arr[middle + 1 + i];
...

Начнем собирать из двух подмассивов отсортированную часть исходного, сравнивая элементы левого подмассива и правого.

...
int i = 0, j = 0, k = left;
while (i < sizeOfLeftPart && j < sizeOfRightPart){
        if (leftPart[i] <= rightPart[j]){
            arr[k] = leftPart[i];
            i++;
        }
        else{
            arr[k] = rightPart[j];
            j++;
        }
        k++;
    }
...

Как только не сработало одно из условий вышеописанного цикла, значит одна из половин закончилась и теперь осталось лишь докинуть "сверху" другую.

...
while (i < sizeOfLeftPart){
    arr[k] = leftPart[i];
    i++;
    k++;
    }

while (j < sizeOfRightPart){
    arr[k] = rightPart[j];
    j++;
    k++;
}
...

Всё)

Итоговый код программы:

void merge(int arr[], int left, int middle, int right){

    int sizeOfLeftPart = middle-left+1;
    int sizeOfRightPart = right-left;
    int leftPart[sizeOfLeftPart], int rightPart[sizeOfRightPart];

    for (int i = 0; i < sizeOfLeftPart; i++)
        leftPart[i] = arr[left + i];
    for (int i = 0; i < sizeOfRightPart; i++)
        rightPart[i] = arr[middle + 1 + i];

    int i = 0, j = 0, k = left;
    while(i < sizeOfLeftPart && j < sizeOfRightPart){
        if (leftPart[i] <= rightPart[j]){
            arr[k] = leftPart[i];
            i++;
        }else{
            arr[k] = rightPart[j];
            j++;
        }
        k++;    
    }

    while (i < sizeOfLeftPart){
        arr[k] = leftPart[i];
        i++;
        k++;
    }

    while (j < sizeOfRightPart){
        arr[k] = rightPart[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r){
    if (l < r){

        int middle = l+(r-l)/2;

        mergeSort(arr, l, middle);
        mergeSort(arr, middle+1, r);

        merge(arr, l, middle, r);
    }
}

Характеристика алгоритма: