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

Алгоритм

Делим массив на половины, сортируем их рекурсивно, сливаем отсортированные части за Θ(N).

Сложность Θ(NlogN) (logN уровней рекурсии, на каждом из которых при слиянии выполняется Θ(N) действий).

Требуется Θ(N) дополнительной памяти (вспомогательный массив t).

void mergeSort(vector<int> &a, vector<int> &t, int l, int r) {
    if (l == r)
        return;

    int m = l + (r - l) / 2;
    mergeSort(a, t, l, m);
    mergeSort(a, t, m + 1, r);

    for (int i = l; i <= r; i++)
        t[i] = a[i];

    int ai = l, bi = m + 1;
    for (int i = l; i <= r; i++) {
        if (bi > r || ai <= m && t[ai] <= t[bi])
            a[i] = t[ai++];
        else
            a[i] = t[bi++];
    }
}

Подсчёт инверсий за Θ(NlogN)

long long mergeSort(vector<int> &a, vector<int> &t, int l, int r) {
    if (l == r)
        return 0;

    int m = l + (r - l) / 2;
    long long inversionCount = 0;
    inversionCount += mergeSort(a, t, l, m);
    inversionCount += mergeSort(a, t, m + 1, r);

    for (int i = l; i <= r; i++)
        t[i] = a[i];

    int ai = l, bi = m + 1;
    for (int i = l; i <= r; i++) {
        if (bi > r || ai <= m && t[ai] <= t[bi]) {
            a[i] = t[ai++];
        } else {
            inversionCount += m - ai + 1;
            a[i] = t[bi++];
        }
    }

    return inversionCount;
}

Ссылки

Теория:

• neerc.ifmo.ru/wiki — Сортировка слиянием
• brestprog.by — Сортировка
• algorithmica.org — Сортировки
• algs4.cs.princeton.edu/lectures — 2.2 Mergesort
• Brilliant.org — Mergesort

Демонстрация:

• Sorting Algorithm Animations — Merge Sort
• VisuAlgo — Sorting

Код:

• indy256/codelibrary/cpp/sort/sort.cpp
• indy256/codelibrary/java/misc/Inversions.java
• ADJA/algos/Other/MergeSort.cpp
• algs4.cs.princeton.edu/code — top-down mergesort, bottom-up mergesort, optimized mergesort

Задачи:

• informatics.mccme.ru — Курс «Поиск и сортировка» — часть 7
• Задачи: Сортировка слиянием
• Задачи: Сортировка