CR: sorting int vector

main.cpp

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

using namespace std;

template<typename RandomAccessIterator1, typename RandomAccessIterator2>
void merge_sort_impl(RandomAccessIterator1 source_begin,
                     RandomAccessIterator1 source_end,
                     RandomAccessIterator2 target_begin,
                     RandomAccessIterator2 target_end)
{
    auto range_length = std::distance(source_begin, source_end);
    
    if (range_length < 2)
    {
        return;
    }
    
    auto left_chunk_length     = range_length >> 1;
    auto source_left_chunk_end = source_begin;
    auto target_left_chunk_end = target_begin;
    
    std::advance(source_left_chunk_end, left_chunk_length);
    std::advance(target_left_chunk_end, left_chunk_length);
    
    merge_sort_impl(target_begin,
                    target_left_chunk_end,
                    source_begin,
                    source_left_chunk_end);
    
    merge_sort_impl(target_left_chunk_end,
                    target_end,
                    source_left_chunk_end,
                    source_end);
    
    std::merge(source_begin,
               source_left_chunk_end,
               source_left_chunk_end,
               source_end,
               target_begin);
}

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

void sort(vector<int> & bar);
void mergeSort(vector<int>&left,vector<int>& right,vector<int>& bars);

#include <chrono>
#include <cstdint>

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();
    }
};

int main() {
    vector<int> nums;
    vector<int> nums2;
    vector<int> nums3;
    
    for (size_t i = 0; i < 1000 * 1000; i++)
    {
        int r = rand();
        nums.push_back(r);
        nums2.push_back(r);
        nums3.push_back(r);
    }
    
    CurrentTime ct;
    
    auto start_time = ct.milliseconds();
    
    sort(nums);
    
    auto end_time = ct.milliseconds();
    
    cout << "OP mergesort in " << (end_time - start_time) << " milliseconds.\n";
    
    start_time = ct.milliseconds();
    
    merge_sort(nums2.begin(), nums2.end());
    
    end_time = ct.milliseconds();
    
    cout << "coderodde mergesort in " << (end_time - start_time)
    << " milliseconds.\n";
    
    start_time = ct.milliseconds();
    
    std::sort(nums3.begin(), nums3.end());
    
    end_time = ct.milliseconds();
    
    cout << "std::sort in " << (end_time - start_time) << " milliseconds.\n";
    cout << boolalpha;
    
    bool agreed = true;
    
    for (int i = 0; i < nums.size(); ++i)
    {
        if (nums[i] != nums2[i] || nums[i] != nums3[i]) {
            agreed = false;
            break;
        }
    }
    
    cout << "Algorithms agree: " << agreed << endl;
    return 0;
}

void sort(vector<int> & bar) {
    if (bar.size() <= 1) return;
    
    int mid = bar.size() / 2;
    vector<int> left;
    vector<int> right;
    
    for (size_t j = 0; j < mid;j++)
        left.push_back(bar[j]);
    for (size_t j = 0; j < (bar.size()) - mid; j++)
        right.push_back(bar[mid + j]);
    
    sort(left);
    sort(right);
    mergeSort(left, right, bar);
}

void mergeSort(vector<int>&left, vector<int>& right, vector<int>& bars)
{
    int nL = left.size();
    int nR = right.size();
    int i = 0, j = 0, k = 0;
    
    while (j < nL && k < nR)
    {
        if (left[j] < right[k]) {
            bars[i] = left[j];
            j++;
        }
        else {
            bars[i] = right[k];
            k++;
        }
        i++;
    }
    while (j < nL) {
        bars[i] = left[j];
        j++; i++;
    }
    while (k < nR) {
        bars[i] = right[k];
        k++; i++;
    }
}