Find the number of inversions in Matlab

Question

On the way of finding number of inversions in array by divide-and-conquer approach I faced with a problem of implementing merge-step: we have two sorted arrays, the task is to count the number of cases when an element of the first array is greater than an element from the second.

For example, if the arrays are v1 = [1,2,4], v2 = [0,3,5], we should count 4 inversions.

So, I implemented the merge-step in Matlab, but I stuck with the problem of how to make it fast.

Firstly, I've tried brute-force approach with

tempArray = arrayfun(@(x) length(find(v2>x)), v1)

It works too slow as well as the next snippet

l = 1;
s = 0;
for ii = 1:n1 
    while(l <= n2 && p1(ii)>p2(l))
        l = l + 1;
    end
    s = s + l - 1;
end

Is there a good way to make it faster?

Edit

Thank you for your answers and approaches! I find interesting things for my further work.

Here is the snippet, which supposed to be the fastest I've tried

n1 = length(vec1); n2 = length(vec2);

uniteOne = [vec1, vec2];

[~, d1] = sort(uniteOne);
[~, d2] = sort(d1); % Find ind-s IX such that B(IX) = A, where B = sort(A)
vec1Slice = d2(1:n1);
finalVecToSolve = vec1Slice - (1:n1);

sum(finalVecToSolve)

Answer 1

Another brute-force approach with bsxfun -

sum(reshape(bsxfun(@gt,v1(:),v2(:).'),[],1))

Or, as @thewaywewalk has mentioned in the comments, use nnz to replacing summing -

nnz(bsxfun(@gt,v1(:),v2(:).'))