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?

• Maikel: Why don't you return std::pair and sum the results, if you don't want to pass a reference?

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.

• Maikel: I just want to note for anyone who does not know that: the way you propose to use requires is already doable with std::enable_ifs. Concepts-TS requires gets really powerful if one needs to test arbitrary expressions without going through todays TMP-mess when doing so.
• Incomputable: @Maikel, I believe g++ doesn't output nice messages "note: disabled by std::enable_if_t" like clang does, so I think the most major reason of why concepts were added would be lost.