# Divide and Conquer algorithm for counting inversions

I've written a program that counts the number of inversions using a Divide and Conquer algorithm, written in C++11.

#include <iostream>
#include <tuple>
#include <vector>

using IntVec = std::vector<int>;

std::tuple<IntVec, long long> count_inv(IntVec xs);
std::tuple<IntVec, long long> count_split_inv(IntVec xs, IntVec ys);

std::tuple<IntVec, long long> count_inv(IntVec xs) {
int n = xs.size();

if (n < 2) return std::make_tuple(xs, 0);

IntVec::iterator middle = xs.begin() + (n / 2);
IntVec left(xs.begin(), middle);
IntVec right(middle, xs.end());

long long left_inv, right_inv, split_inv;
IntVec as, bs, cs;
std::tie(as, left_inv) = count_inv(left);
std::tie(bs, right_inv) = count_inv(right);
std::tie(cs, split_inv) = count_split_inv(as, bs);
return std::make_tuple(cs, left_inv + right_inv + split_inv);
}

std::tuple<IntVec, long long> count_split_inv(IntVec xs, IntVec ys) {
int n = xs.size() + ys.size();
IntVec zs(n);
long long split_inv = 0;

int i = 0, j = 0, k = 0;
for (; k < n && i < xs.size() && j < ys.size(); ++k) {
if (xs[i] <= ys[j]) {
zs[k] = xs[i];
++i;
} else {
zs[k] = ys[j];
++j;
split_inv += xs.size() - i;
}
}

for (; i < xs.size(); ++k, ++i)
zs[k] = xs[i];

for (; j < ys.size(); ++k, ++j)
zs[k] = ys[j];

return std::make_tuple(zs, split_inv);
}

int main() {
std::vector<int> xs;
int x;
while (std::cin >> x) {
xs.push_back(x);
}

IntVec ys;
long long inv;
std::tie(ys, inv) = count_inv(xs);
std::cout << inv << std::endl;
return 0;
}


I find that the code is very verbose in some areas, such as specifying the type of the tuple. Also, parts of it are confusing. How could I rewrite this code such that it is more concise and clearer?

• Number of inversions of what? And according to which rules? Also, it's "divide and conquer", not the other way around... Oct 25, 2015 at 17:15
• @Deduplicator Whoops, no idea why I wrote it that way. It should print out the number of inversions of the array of numbers, assuming that the numbers are to be sorted in ascending order. Oct 27, 2015 at 14:46
• Do you mean number of swaps, instead of inversions? I'm whistling in the dark here, as I still have no idea what your program does (should do), or why... Oct 27, 2015 at 14:52
• @Deduplicator I believe that an inversion is a pair of array entries that are in the wrong order. In other words every pair (i,j) where i < j && array[i] > array[j]. At least, this is what would make sense, because this program is using the "mergesort method" of counting the number of inversions in an array. See this link, for example.
– JS1
Oct 27, 2015 at 20:12
• What JS1 wrote is what I'm looking for. I do not need to find the inversions themselves, just the number of inversions. Oct 28, 2015 at 13:29

# More clear by using extra argument?

If you passed in a count by reference to each function, and each function incremented this count instead of returning a new count in a tuple, the code might look cleaner. For example, this:

IntVec as, bs, cs;
std::tie(as, left_inv) = count_inv(left);
std::tie(bs, right_inv) = count_inv(right);
std::tie(cs, split_inv) = count_split_inv(as, bs);
return std::make_tuple(cs, left_inv + right_inv + split_inv);


would become this:

IntVec as = count_inv(left, count);
IntVec bs = count_inv(right, count);
return count_split_inv(as, bs, count);


And in main(), this:

long long inv;
std::tie(ys, inv) = count_inv(xs);


would become this:

long long inv = 0;
count_inv(xs, inv);

• I'm not certain if it's good practice to use pointers in this case. Nov 3, 2015 at 14:36
• @wei2912 As opposed to creating tuples and returning them? Why are you opposed to using pointers?
– JS1
Nov 3, 2015 at 18:10
• It certainly looks cleaner, but in these calls to count_inv(xs, inv), it's not entirely clear that the inv/count variables will be changed as a side-effect. I also agree that returning a tuple is much worse, so I don't have an imediate solution for this. Jan 28, 2016 at 11:31