Counting inversions in C++ via mergesort and vectors
What kind of efficiency?

You ask for efficiency, but don't clarify whether you want programmer or processor efficiency. And, at least sometimes, the two can both be improved simultaneously by leveraging the right pre-existing tools, so it's worth considering programmer efficiency.

Programmer efficiency comes in at least three general categories:


Writing less code:

I would be strongly tempted to confirm whether this can be written to leverage std::sort with a custom type that implements a counter in its overload to std::swap. If you can transform the problem like this, you don't have to worry about coding a merge sort correctly, and should have less code.
Writing clearer code:

The arguments to mergeAndCount are named vec, p, q, and r, and have no comments that clarify the meaning of p, q, and r (inversion's arguments p and r suffer similarly). Furthermore mergeAndCount's local variables are named L and R. What do these mean? The parameters appear to be local indices for special spots in the vector; perhaps they could be named accordingly.

As an extension of "naming things is important", consider also renaming inversion to use a verb instead of a noun. Something like invert is typically better than inversion; something that indicates what it's doing could be better still. Perhaps sortAndCount?

Sometimes avoiding raw loops can help. For example, the loops that fill L and R could be written with std::copy. But better yet, you could construct them in place with the range constructor:

vector&lt;int&gt; L(&amp;vec[p], &amp;vec[q + 1]);
vector&lt;int&gt; R(&amp;vec[q + 1], &amp;vec[r + 1]);


Two side comments here: your use of a final index rather than one past final (closed range instead of open range) conflicts with the standard library. If main called inversion with .size() instead of .size() - 1, and everything else was updated to match, a number of + 1 and/or - 1 items should disappear, starting with the three + 1 instances in my little code excerpt.

Second, I'm uncertain what I think of the use of a sentinel as opposed to verifying the index location. Doesn't it have a side effect that would harm lists with that number? While the current problem definition excludes use of the sentinel, problems have a tendency of changing over time; attempts to reuse code may result in using code that isn't suited for the new problem.
Making it harder to screw up:

The indices you pass into inversion and mergeAndCount represent very important values that never change. You should consider marking them const in order to avoid losing the ends of your ranges.


On the flip side, processor efficiency comes from many things that often compete with programmer efficiency. Here are a couple that could be relevant.


Avoiding allocations:

Often allocating in a loop is a source of run-time inefficiency. Note, for example, that std::merge requires input and output ranges, rather than allocating its own helper ranges internally. This allows std::sort to allocate them once and reuse them as necessary. (This comment conflicts with the above suggestion to use the range constructor.)
Memory access patterns:

Scanning through memory linearly is often the fastest way to access it. Your code does a pretty good job of this already, so without profiling there's little I can offer here.