Implementation of merge sort as an exercise.

merge_sort.hpp

#pragma once

#include <algorithm>
#include <vector>

namespace {

    template <typename IT>
    void inner_merge(IT begin, IT middle, IT end) {
        using Container = std::vector<typename std::iterator_traits<IT>::value_type>;
        Container copy_a(std::distance(begin, middle));
        Container copy_b(std::distance(middle, end));
        std::copy(begin, middle, copy_a.begin());
        std::copy(middle, end, copy_b.begin());
        
        auto i = begin;
        auto ai = copy_a.begin();
        auto bi = copy_b.begin();
        while (ai != copy_a.end() && bi != copy_b.end()) {
            *i = (*ai > *bi) ? *bi : *ai;
            if (*ai > *bi) bi++;
            else ai++;
            i = i + 1;
        }
        
        auto ne_begin = (ai == copy_a.end()) ? bi : ai;
        auto ne_end = (ai == copy_a.end()) ? copy_b.end() : copy_a.end();
        std::copy(ne_begin, ne_end, i);
    }
    
}

template <typename IT>
void merge_sort(IT begin, IT end) {
    auto s = std::distance(begin, end); // size
    auto h = s / 2; // half floored

    if (s == 1) return;
    merge_sort(begin, begin + h);
    merge_sort(begin + h, end);
    inner_merge(begin, begin + h, end);
}