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 &lt;iostream&gt;
#include &lt;tuple&gt;
#include &lt;vector&gt;

using IntVec = std::vector&lt;int&gt;;

std::tuple&lt;IntVec, long long&gt; count_inv(IntVec xs);
std::tuple&lt;IntVec, long long&gt; count_split_inv(IntVec xs, IntVec ys);

std::tuple&lt;IntVec, long long&gt; count_inv(IntVec xs) {
    int n = xs.size();

    if (n &lt; 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&lt;IntVec, long long&gt; 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 &lt; n &amp;&amp; i &lt; xs.size() &amp;&amp; j &lt; ys.size(); ++k) {
        if (xs[i] &lt;= ys[j]) {
            zs[k] = xs[i];
            ++i;
        } else {
            zs[k] = ys[j];
            ++j;
            split_inv += xs.size() - i;
        }
    }

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

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

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

int main() {
    std::vector&lt;int&gt; xs;
    int x;
    while (std::cin &gt;&gt; x) {
        xs.push_back(x);
    }

    IntVec ys;
    long long inv;
    std::tie(ys, inv) = count_inv(xs);
    std::cout &lt;&lt; inv &lt;&lt; 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?
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);