main.cpp

#include "mergesort.h"
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <iostream>
#include <random>
#include <vector>

using std::boolalpha;
using std::copy;
using std::cout;
using std::endl;
using std::equal;
using std::ostream_iterator;
using std::stable_sort;
using std::vector;

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

template<typename RandIt>
static void print_int_sequence(RandIt begin, RandIt end)
{
    cout << *begin;
    begin++;
    
    while (begin != end)
    {
        cout << ' ' << *begin;
        begin++;
    }
    
    cout << endl;
}

static vector<int> get_random_int_vector(size_t length)
{
    vector<int> ret;
    std::random_device rd;
    std::mt19937 rng(rd());
    std::uniform_int_distribution<int> uni;
    
    for (size_t i = 0; i != length; ++i)
    {
        ret.push_back(uni(rng));
    }
    
    return ret;
}

static const size_t SEQUENCE_LENGTH = 10 * 1000 * 1000;

int main(int argc, const char * argv[]) {
    vector<int> vec1 = get_random_int_vector(SEQUENCE_LENGTH);
    vector<int> vec2(SEQUENCE_LENGTH);
    vector<int> vec3(SEQUENCE_LENGTH);
    
    copy(vec1.begin(), vec1.end(), vec2.begin());
    copy(vec1.begin(), vec1.end(), vec3.begin());
    
    CurrentTime ct;
    
    auto start = ct.milliseconds();
    mergeSort(vec1, 0, vec1.size() - 1);
    auto end = ct.milliseconds();
    
    cout << "OP mergeSort in " << (end - start) << " milliseconds." << endl;
    
    start = ct.milliseconds();
    mergeSort(vec2);
    end = ct.milliseconds();
    
    cout << "cr mergeSort in " << (end - start) << " milliseconds." << endl;
    
    start = ct.milliseconds();
    stable_sort(vec3.begin(), vec3.end());
    end = ct.milliseconds();
    
    cout << "stable_sort in " << (end - start) << " milliseconds." << endl;
    
    bool agree = equal(vec1.begin(), vec1.end(), vec2.begin(), vec2.end()) &&
                 equal(vec1.begin(), vec1.end(), vec3.begin(), vec3.end());
    
    cout << "Algorithms agree: " << boolalpha << agree << endl;
    return 0;
}

mergesort.h

#include <algorithm>
#include <iterator>
#include <vector>

template<typename T> void merge(std::vector<T> &vec, int left, int mid, int right )
{
    int i=left;
    int j=mid+1;
    int k=0;
    int size = (right - left) +1;
    std::vector<T> result(size);
    
    while(i <= mid && j <= right)  result[k++] = (vec[i] < vec[j])? vec[i++] : vec[j++];
    while(i <= mid)                result[k++] = vec[i++];
    while(j <= right)              result[k++] = vec[j++];
    
    for(k=0; k < size; k++)
    {
        vec[left+k] = result[k];
    }
}

template<typename T> void mergeSort(std::vector<T> &vec, int left, int right)
{
    // Base Case --- Left is greater than right, then don't execute.
    
    if (left<right){
        
        // get mid point.
        int mid = left + (right-left)/2 ;
        // recursive merge sort until array(half) is 1 in length.
        mergeSort(vec, left, mid);
        mergeSort(vec, mid+1, right);
        // merge both arrays.
        merge(vec, left, mid, right);
    }
}

template<typename RandIt1, typename RandIt2>
void mergeSort(RandIt1 source_begin,
               RandIt1 source_end,
               RandIt2 target_begin,
               RandIt2 target_end)
{
    auto range_length = std::distance(source_begin, source_end);
    
    if (range_length < 2)
    {
        return;
    }
    
    auto left_subrange_length = range_length >> 1;
    
    mergeSort(target_begin,
              target_begin + left_subrange_length,
              source_begin,
              source_begin + left_subrange_length);
    
    mergeSort(target_begin + left_subrange_length,
              target_end,
              source_begin + left_subrange_length,
              source_end);
    
    std::merge(source_begin,
               source_begin + left_subrange_length,
               source_begin + left_subrange_length,
               source_end,
               target_begin);
}

template<typename RandIt>
void mergeSort(RandIt begin, RandIt end)
{
    auto range_length = std::distance(begin, end);
    
    if (range_length < 2)
    {
        return;
    }
    
    using value_type = typename std::iterator_traits<RandIt>::value_type;
    std::vector<value_type> aux(begin, end);
    mergeSort(aux.begin(), aux.end(), begin, end);
}

template<typename T>
void mergeSort(std::vector<T>& vec)
{
    mergeSort(vec.begin(), vec.end());
}