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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску

Алгоритм

Делим массив на половины, сортируем их рекурсивно, сливаем отсортированные части за Θ(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;
}

Ссылки

Теория:

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

Код:

Задачи: