# 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... – Deduplicator Oct 25 '15 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. – wei2912 Oct 27 '15 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... – Deduplicator Oct 27 '15 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 '15 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. – wei2912 Oct 28 '15 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. – wei2912 Nov 3 '15 at 14:36
• @wei2912 As opposed to creating tuples and returning them? Why are you opposed to using pointers? – JS1 Nov 3 '15 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. – Cássio Renan Jan 28 '16 at 11:31