cr_mergesort.cpp

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <chrono>
#include <cstdint>
#include <random>

void mergeSort(std::vector<int>::iterator begin,
               std::vector<int>::iterator end);

void merge(std::vector<int>::iterator begin,
           std::vector<int>::iterator middle,
           std::vector<int>::iterator end);

template<typename RandomIter1, typename RandomIter2>
void merge(RandomIter1 begin,
           RandomIter1 middle,
           RandomIter1 end,
           RandomIter2 aux) {
    RandomIter1 left = begin;
    RandomIter1 right = middle;
    RandomIter1 left_bound = middle;
    RandomIter1 right_bound = end;
    
    while (left != left_bound and right != right_bound) {
        if (*right < *left) {
            *aux = *right;
            ++right;
        } else {
            *aux = *left;
            ++left;
        }
        
        ++aux;
    }
    
    std::copy(left, left_bound, aux);
    std::copy(right, right_bound, aux);
}

template<typename RandomIter1, typename RandomIter2>
void merge_sort(RandomIter1 source_begin,
                RandomIter1 source_end,
                RandomIter2 target_begin,
                RandomIter2 target_end) {
    auto distance = std::distance(source_begin, source_end);
    
    if (distance < 2) {
        return;
    }
    
    RandomIter1 source_middle = source_begin;
    RandomIter2 target_middle = target_begin;
    std::advance(source_middle, distance >> 1); // distance >> 1 is the same as
                                         // distance / 2
    std::advance(target_middle, distance >> 1);
    
    merge_sort(target_begin,
               target_middle,
               source_begin,
               source_middle);
    
    merge_sort(target_middle,
               target_end,
               source_middle,
               source_end);
    
    merge(source_begin,
          source_middle,
          source_end,
          target_begin);
}

template<typename RandomIter>
void merge_sort(RandomIter begin, RandomIter end) {
    auto distance = std::distance(begin, end);
    
    if (distance < 2) {
        return;
    }
    
    using value_type = typename std::iterator_traits<RandomIter>::value_type;
    value_type* aux = new value_type[distance];
    std::copy(begin, end, aux);
    merge_sort(aux, aux + distance, begin, end);
    delete[] aux;
}

void print(const std::vector<int> &v);

uint64_t milliseconds()
{
    std::chrono::high_resolution_clock m_clock;
    return std::chrono::duration_cast<std::chrono::milliseconds>
    (m_clock.now().time_since_epoch()).count();
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::random_device r;
    std::default_random_engine e1(r());
    std::uniform_int_distribution<int> uniform_dist(0, 1000000);
    std::vector<int> v;
    
    for (int i = 0; i < 1000000; ++i) {
        v.push_back(uniform_dist(e1));
    }
    
    std::vector<int> v2(v);
    
    uint64_t start = milliseconds();
    mergeSort(v.begin(), v.end());
    uint64_t end = milliseconds();
    
    std::cout << "OP time: " << (end - start) << " milliseconds." << std::endl;
    
    start = milliseconds();
    merge_sort(v2.begin(), v2.end());
    end = milliseconds();
    
    std::cout << "coderodde time: " << (end - start) << " milliseconds."
              << std::endl;
    std::cout << "Algorithms agree: " << std::boolalpha
              << std::equal(v.begin(),
                            v.end(),
                            v2.begin(),
                            v2.end())
              << std::endl;
    return 0;
}

void mergeSort(std::vector<int>::iterator begin, std::vector<int>::iterator end) {
    auto distance = std::distance(begin, end);
    
    if (distance < 2) {
        return;
    }
    
    auto middle = begin;
    std::advance(middle, distance / 2);
    mergeSort(begin, middle);
    mergeSort(middle, end);
    merge(begin, middle, end);
}

void merge(std::vector<int>::iterator begin,
           std::vector<int>::iterator middle,
           std::vector<int>::iterator end) {
    auto distance = std::distance(begin, end);
    std::vector<int> aux(distance);
    
    auto left = begin;
    auto left_bound = middle;
    auto right = middle;
    auto right_bound = end;
    size_t aux_index = 0;
    
    while (left != left_bound && right != right_bound) {
        if (*right < *left) {
            aux[aux_index++] = *right;
            ++right;
        } else {
            aux[aux_index++] = *left;
            ++left;
        }
    }
    
    std::copy(left, left_bound, &aux[aux_index]);
    std::copy(right, right_bound, &aux[aux_index]);
    std::copy(aux.begin(), aux.end(), begin);
}

void print(const std::vector<int> &v) {
    for (const auto &i : v) {
        std::cout << i << " ";
    }
    
    std::cout << std::endl;
}