Merge Sort

Массив делится ровно пополам (без всякой оценки содержимого — в отличие от quicksort, здесь не нужен pivot), каждая половина рекурсивно сортируется тем же алгоритмом, а затем две уже отсортированные половины сливаются в одну: заводятся два указателя на начала половин, на каждом шаге сравниваются элементы под указателями, меньший переносится в результирующий массив, указатель сдвигается. В отличие от quicksort, вся содержательная работа происходит после рекурсии (на этапе слияния), а не до неё — отсюда и потребность в дополнительном массиве для хранения результата слияния.The array is split exactly in half (with no evaluation of its contents — unlike quicksort, no pivot is needed here), each half is recursively sorted by the same algorithm, and then the two already-sorted halves are merged into one: two pointers are set at the start of each half, at each step the elements under the pointers are compared, the smaller one is copied into the result array, and its pointer advances. Unlike quicksort, all the substantive work happens after the recursion (during the merge step), not before it — hence the need for an extra array to hold the merge result.

void merge(std::vector<int>& a, int lo, int mid, int hi) {
    std::vector<int> buf;
    int i = lo, j = mid + 1;
    while (i <= mid && j <= hi)
        buf.push_back(a[i] <= a[j] ? a[i++] : a[j++]); // <= сохраняет стабильность// <= keeps it stable
    while (i <= mid) buf.push_back(a[i++]);
    while (j <= hi)  buf.push_back(a[j++]);
    std::copy(buf.begin(), buf.end(), a.begin() + lo);
}

void merge_sort(std::vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    merge_sort(a, lo, mid);
    merge_sort(a, mid + 1, hi);
    merge(a, lo, mid, hi);
}

Строка a[i] <= a[j] ? a[i++] : a[j++] — вот где именно рождается стабильность: при равенстве элементов предпочтение всегда отдаётся левой половине, то есть элементу, который в исходном массиве стоял раньше. Замена на строгое < сломала бы стабильность, хотя результат сортировки остался бы численно тем же.The line a[i] <= a[j] ? a[i++] : a[j++] is exactly where stability comes from: on a tie, preference always goes to the left half — the element that came earlier in the original array. Swapping in a strict < would break stability, even though the numerically sorted result would stay the same.

Показан эквивалентный по результату восходящий (bottom-up) merge sort: блоки размера 1 сливаются в блоки размера 2, те — в блоки размера 4, и так далее. Синяя и голубая рамки — два сливаемых блока, красная — элемент под сравниваемым указателем, зелёная заливка — уже слитый и потому финальный на этом уровне блок.Shown here is a result-equivalent bottom-up merge sort: blocks of size 1 merge into blocks of size 2, those into blocks of size 4, and so on. The blue and cyan outlines are the two blocks being merged, red is the element under the compared pointer, green fill marks a block already merged and thus final at this level.

В отличие от quicksort, разбиение здесь не зависит от содержимого массива — оно всегда ровно пополам, независимо от входных данных. Это делает рекуррентность T(n) = 2T(n/2) + O(n) точной, а не средней оценкой — по Master Theorem (случай 2, 2.1.2) T(n) = Θ(n log n) всегда, включая худший случай. Цена этой гарантии — O(n) дополнительной памяти на буфер слияния (в отличие от in-place quicksort/heapsort).Unlike quicksort, the split here doesn't depend on the array's contents — it's always exactly in half, regardless of input. This makes the recurrence T(n) = 2T(n/2) + O(n) exact rather than an average-case estimate — by the Master Theorem (case 2, 2.1.2), T(n) = Θ(n log n) always, worst case included. The price of that guarantee is O(n) extra memory for the merge buffer (unlike in-place quicksort/heapsort).