In place merge sort

inplace_merge_sort.cpp

#include <iostream>
#include <algorithm>
#include <cassert>
#include <iterator>

using namespace std;


template <typename ForwardIterator>
void merge_into(ForwardIterator from, ForwardIterator mid, ForwardIterator to, ForwardIterator buffer) {
    auto from1 = from;
    auto to1 = mid;
    auto from2 = mid;
    auto to2 = to;
    while (from1 != to1 && from2 != to2) {
        if (*from1 < *from2) {
            std::swap(*from1, *buffer);
            ++from1;
        } else {
            std::swap(*from2, *buffer);
            ++from2;
        }
        ++buffer;
    }
    swap_ranges(from1, to1, buffer);
    swap_ranges(from2, to2, buffer);
}

// just an ordinary merge sort with buffer as a temporary storage
template <typename ForwardIterator>
void merge_sort(ForwardIterator from, ForwardIterator to, ForwardIterator buffer) {
    auto dist = distance(from, to);
    if (dist <= 1) { // already sorted
        return;
    }
    auto middle = next(from, dist / 2);
    // XXXXXFFFFFF ; X is unsorted, F is buffer
    merge_sort(from, middle, buffer);
    // AAXXXFFFFFF ; As are sorted
    merge_sort(middle, to, buffer);
    // AABBBFFFFFF ; Bs are sorted
    merge_into(from, middle, to, buffer);
    // FFFFFCCCCCF ; Cs are sorted (composed of As and Bs)
    swap_ranges(from, to, buffer);
    // CCCCCFFFFFF
}

template <typename ForwardIterator>
void merge_sort_inplace(ForwardIterator from, ForwardIterator to) {
    // XXXXXXXXXXX ; initial arrangement, Xs are unsorted
    auto sorted_end = from; // fake sorted range of length 0 lol
    while (distance(sorted_end, to) > 1) {
        // AAAAAXXXXXX ; As were sorted on previous steps
        auto sorted_count = distance(from, sorted_end);
        auto unsorted_count = distance(sorted_end, to);
        auto next_sorted_end = next(sorted_end, unsorted_count / 2);
        auto buffer_size = distance(next_sorted_end, to);

        merge_sort(sorted_end, next_sorted_end, next_sorted_end);
        // AAAAABBBXXX ; As and Bs are sorted now
        rotate(from, next_sorted_end, to);
        // XXXAAAAABBB ; rotate for merging convenience
        merge_into(next(from, buffer_size), next(from, buffer_size + sorted_count), to, from);
        // CCCCCCCCXXX; Cs are sorted!
        sorted_end = next_sorted_end;
    }
    if (sorted_end == to) {
        return;
    }
    assert(distance(sorted_end, to) == 1); // just a sanity check
    auto insert_at = std::lower_bound(from, sorted_end, *sorted_end);
    rotate(insert_at, sorted_end, to);
}

int main() {
    mt19937 engine(114321);
    uniform_int_distribution<int64_t> values(-1000, 1000);
    uniform_int_distribution<uint32_t> lengths(0, 10000);

    for (int t = 0; t < 100; t++) {
        auto len = lengths(engine);
        auto test = vector<int64_t >(len);
        for (int i = 0; i < len; i++) {
            test[i] = values(engine);
        }
        merge_sort_inplace(test.begin(), test.end());
        assert(is_sorted(test.begin(), test.end()));
    }
    return 0;
}