Сортировка слиянием и подсчёт инверсий

Сортировка слиянием строится из одной вспомогательной задачи, которую полезно уметь решать саму по себе.

Слияние двух отсортированных массивов

Даны два массива, каждый отсортирован по неубыванию. Нужен третий, содержащий все их элементы и тоже отсортированный.

Заводим два указателя, по одному на каждый массив. Наименьший из ещё не взятых элементов — это минимум из двух, на которые указатели смотрят. Берём его, сдвигаем соответствующий указатель, повторяем.

vector<int> c(n + m);
int i = 0, j = 0, k = 0;
while (i < n && j < m)
    c[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
while (i < n) c[k++] = a[i++];
while (j < m) c[k++] = b[j++];

Когда один массив кончился, остаток другого дописывается как есть — он уже отсортирован и весь больше того, что уже взято.

Указатели только растут, каждый проходит свой массив один раз, значит слияние работает за $O(n + m)$.

Нестрогое сравнение a[i] <= b[j] выбрано не случайно: при равенстве элемент берётся из левого массива. Это понадобится дальше — и для устойчивости, и для подсчёта инверсий.

Сама сортировка

Разобьём массив пополам, отсортируем каждую половину и сольём. Как сортировать половины? Точно так же — разбить пополам и слить. Остановиться можно, когда кусок стал длины 1: такой массив уже отсортирован.

graph TD
  A["8 3 5 1 9 2"] --> B["8 3 5"]
  A --> C["1 9 2"]
  B --> D["8"]
  B --> E["3 5"]
  C --> F["1"]
  C --> G["9 2"]
  E --> H["3"]
  E --> I["5"]
  G --> J["9"]
  G --> K["2"]

Спуск идёт до одиночных элементов, потом всё сливается обратно снизу вверх.

// Границы — полуинтервал [l, r): так меньше плюс-минус единиц в коде.
void merge_sort(vector<int>& a, int l, int r) {
    if (r - l <= 1) return;
    int mid = l + (r - l) / 2;
    merge_sort(a, l, mid);
    merge_sort(a, mid, r);
    // слить a[l..mid) и a[mid..r) во временный массив и записать обратно
}

Про mid: писать (l + r) / 2 тоже можно, но l + (r - l) / 2 не переполняется при больших границах и означает то же самое.

Почему n log n

Каждый спуск делит массив пополам, значит уровней рекурсии примерно $\log_2 n$. На каждом уровне все слияния вместе просматривают каждый элемент один раз, то есть стоят $O(n)$. Итого $O(n \log n)$.

Это уже настоящая сортировка: при $n$ до миллиона она проходит.

Устойчивость

Сортировка слиянием устойчива, и это не случайность, а следствие одной строки: при равенстве элемент берётся из левой половины.

Левая половина в исходном массиве стояла раньше правой. Значит, из двух равных элементов первым в результат попадёт тот, что был левее, — а это и есть определение устойчивости. Поменяйте <= на <, и свойство пропадёт, хотя массив по-прежнему будет отсортирован.

Именно поэтому stable_sort в C++ реализуют через слияние, а не через быструю сортировку: у той порядок равных не сохраняется в принципе, потому что разделение перебрасывает элементы через весь массив.

Версия снизу вверх

Рекурсия здесь не обязательна. Можно сливать отрезками растущей длины: сначала по одному, потом по два, по четыре и так далее.

for (int width = 1; width < n; width *= 2)
    for (int left = 0; left < n; left += 2 * width) {
        int mid = min(left + width, n);
        int right = min(left + 2 * width, n);
        // слить a[left..mid) и a[mid..right)
    }

Работает то же самое время, но без рекурсии и без риска переполнить стек. На больших массивах это заметно: миллион элементов дают глубину 20 — не страшно, но в задачах, где рекурсия уже используется на что-то другое, запас лишним не бывает.

Про память

Слияние нельзя сделать на месте без потери простоты: результат приходится складывать в отдельный массив, а потом копировать обратно. Значит, нужно $O(n)$ дополнительной памяти — это главный недостаток по сравнению с быстрой и пирамидальной сортировками.

Заводить временный массив внутри каждого вызова не стоит: выделение памяти дорого, и на $\log n$ уровнях это заметно. Правильно — выделить буфер один раз снаружи и передавать его.

Инверсии

Пара индексов $i < j$ образует инверсию, если $a_i > a_j$. Число инверсий — мера того, насколько массив далёк от отсортированного: у отсортированного их ноль, у развёрнутого $\tfrac{n(n-1)}{2}$.

В лоб это два вложенных цикла и $O(n^2)$. Но инверсии умеет считать сам merge sort, и почти бесплатно.

Посмотрим на одно слияние. Левая половина и правая половина уже отсортированы. Пусть на очередном шаге мы берём элемент из правой половины — значит, он меньше того, на который смотрит указатель левой половины. А раз левая половина отсортирована, он меньше и всех, кто в ней остался.

Значит, в этот момент нашлось ровно столько инверсий, сколько элементов осталось в левой половине:

if (a[i] <= b[j]) {
    c[k++] = a[i++];
} else {
    inversions += n - i;   // вот и все инверсии этого шага
    c[k++] = b[j++];
}

Одна строка. И здесь становится видно, зачем при равенстве брать элемент слева: иначе равные пары посчитались бы как инверсии, хотя инверсией пара равных не является.

Ответ бывает большим: при $n = 10^5$ инверсий до $5 \cdot 10^9$, и в 32-битный тип это не влезает.

Готовое слияние в C++

В <algorithm> есть std::merge — он сливает два уже отсортированных диапазона:

merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c));

Ничего он не возвращает: результат дописывается туда, куда указывает пятый аргумент. Если размер результата известен заранее, лучше выделить память сразу, а не полагаться на back_inserter.