Counting inversions with merge sort

Question

I am piggybacking an iterator-based implementation of merge-sort to count array inversions. My first correct solution looks as follows:

#include <vector>
#include <iterator>
#include <stdio.h>

template<typename It>
std::vector<typename It::value_type> SortAndCountInversionsSubroutine(const It begin, const It middle, const It end, unsigned int& count)
{
    std::vector<typename It::value_type> v;
    It left{ begin }, right{ middle };
    while (left != middle && right != end)
    {
        if (*left <= *right)
        {
            v.push_back(*left++);
        }
        else
        {
            count+= std::distance(left, middle);
            v.push_back(*right++);
        }
    }
    v.insert(v.end(), left, middle);
    v.insert(v.end(), right, end);
    return v;
}

template<typename It>
void SortAndCountInversions(It begin, It end,unsigned int& count)
{ 
    auto size = std::distance(begin, end);
    if (size < 2)
        return;
    auto mid = std::next(begin, size / 2);
    SortAndCountInversions(begin, mid, count);
    SortAndCountInversions(mid, end, count);
    auto v = SortAndCountInversionsSubroutine(begin, mid, end, count);
    std::move(v.cbegin(), v.cend(), begin);
}

The implementation can be used as follows:

std::vector<int> v1{ 1, 3, 5, 2, 4, 6 };
unsigned int inversionCount = 0;
unsigned int expectedCount = 3;
SortAndCountInversions(v1.begin(), v1.end(), inversionCount);
Assert::AreEqual(expectedCount, inversionCount);

inversionCount = 0;
expectedCount = 5;
std::vector<int> v2{ 1, 20, 6, 4, 5 };
SortAndCountInversions(v2.begin(), v2.end() , inversionCount = 0);
Assert::AreEqual(expectedCount, inversionCount);

I am looking for any suggestions to improve my code. Particularly, I would like to return the inversion count as a return value, instead of a parameter reference. Any ideas?

Answer 1

Looks nice and clean.

One thing to note:

With Iterators Const Iterator is not the same as Iterator_Const. The first means you will not change the iterator while the second means you will not change what the iterator points at. You actually want to mean the second the first one is rarely useful.

<ReturnType> SortAndCountInversionsSubroutine(
                 const It begin, const It middle, const It end,
            //   ^^^^^           ^^^^^             ^^^^
                 unsigned int& count)

That's not a very useful const. Just use:

template<typename It>
// When C++ concepts get added just uncomment the line below.
// requires std::is_const<typename std::iterator_traits<It>::reference_type>::value
<ReturnType> SortAndCountInversionsSubroutine(
                 It begin, It middle, It end,
                 unsigned int& count)

I "might" change this:

auto v = SortAndCountInversionsSubroutine(begin, mid, end, count);
std::move(v.cbegin(), v.cend(), begin);

I might move the std::move() into the SortAndCountInversionsSubroutine() the trouble with that is you need to change the iterators from being iterator_const (once you have fixed the first point) to non const. The advantage of course is that you don't have to return a vectorfrom a function.