Сортировка слиянием (Merge sort)

Сортировка слиянием - это эффективный алгоритм сортировки, использующий подход "разделяй и властвуй". Он разбивает массив на две половины, рекурсивно сортирует их, а затем объединяет отсортированные половины.

Алгоритм

Алгоритм сортировки слиянием работает следующим образом:

1. Разделить массив на две половины.
2. Рекурсивно сортировать каждую половину.
3. Объединить две отсортированные половины в один отсортированный массив.

Анализ сложности

• Временная сложность сортировки слиянием: Во всех случаях $O(n\log n)$, где $n$ - количество элементов.
• Пространственная сложность сортировки слиянием: $O(n)$, так как требуется дополнительное пространство для временного хранения подмассивов.

Реализация

Приведём примеры реализации сортировки слиянием:

Python

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

C++

#include <vector>

void merge(std::vector<int>& arr, int const left, int const mid, int const right) {
    auto const subArrayOne = mid - left + 1;
    auto const subArrayTwo = right - mid;

    std::vector<int> leftArray(subArrayOne), rightArray(subArrayTwo);

    for (auto i = 0; i < subArrayOne; i++)
        leftArray[i] = arr[left + i];
    for (auto j = 0; j < subArrayTwo; j++)
        rightArray[j] = arr[mid + 1 + j];

    auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0;
    int indexOfMergedArray = left;

    while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo) {
        if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) {
            arr[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
            indexOfSubArrayOne++;
        } else {
            arr[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
            indexOfSubArrayTwo++;
        }
        indexOfMergedArray++;
    }
    while (indexOfSubArrayOne < subArrayOne) {
        arr[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
        indexOfSubArrayOne++;
        indexOfMergedArray++;
    }
    while (indexOfSubArrayTwo < subArrayTwo) {
        arr[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
        indexOfSubArrayTwo++;
        indexOfMergedArray++;
    }
}

void mergeSort(std::vector<int>& arr, int const begin, int const end) {
    if (begin >= end)
        return;

    auto mid = begin + (end - begin) / 2;
    mergeSort(arr, begin, mid);
    mergeSort(arr, mid + 1, end);
    merge(arr, begin, mid, end);
}

Java

public void mergeSort(int[] arr, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;

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

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

private void merge(int[] arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    int[] L = new int[n1];
    int[] R = new int[n2];

    for (int i = 0; i < n1; ++i)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[m + 1 + j];

    int i = 0, j = 0;

    int k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

Заключение

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

Одним из ключевых преимуществ сортировки слиянием является её стабильность и предсказуемость производительности, что делает её предпочтительным выбором в ситуациях, где важна гарантия времени выполнения. Однако, необходимость в дополнительном пространстве для хранения подмассивов может быть ограничивающим фактором в средах с ограниченными ресурсами памяти.