Merge-and-count(L1,L2)

%This program merges two sorted lists L1 and L2, returns the sorted 
% merged list and also a count of the number of inversions where
%here an inversion is a pair <L1(i),L2(j)> with L1(i) > L2(j).

   n1:= array size of L1;
   n2:= array size of L2;
   i := 1 ; j :=1 ; k := 1 ; r :=0;
   define new array L of size n1+n2;

   While k <= n1 + n2
     if a(i) <= b(j) 
       then L(k) := L1(i) ; i := i+1
     else 
       L(k) := L2(j) ; r := r + n1 - i + 1 ; j := j + 1
     endif
     k := k + 1
   endwhile

   if i <= n1 
     then for m = i .. n1
            L(k + m - i)) := L1(m)  
          endfor
     else for m = j .. n2
            L(k + m - 1) := L2(m)
          endfor
   endif
   return (r,L)