I had a problem from the book
Give an algorithm that determines the number of inversions in any permutation on n elements in $O(n \lg n)$ worst-case time. (Hint: Modify merge sort.)
I couldn't solve it and decided to take a hint. So there's a claim that is proved, but I don't understand this.
To start, let us define a merge-inversion as a situation within the execution of merge sort in which the MERGE procedure, after copying $A[p..q]$ to $L$ and $A[q + 1..r]$ to $R$, has values $x$ in $L$ and $y$ in $R$ such that $x$>$y$. Consider an inversion $[i,j]$, and let $x=A[i]$ and $y=A[j]$, so that $i < j$ and $x > y$. We claim that if we were to run merge sort, there would be exactly one merge-inversion involving $x$ and $y$. To see why, observe that the only way in which array elements change their positions is within the MERGE procedure. Moreover, since MERGE keeps elements within $L$ in the same relative order to each other, and correspondingly for $R$, the only way in which two elements can change their ordering relative to each other is for the greater one to appear in $L$ and the lesser one to appear in $R$. Thus, there is at least one merge-inversion involving $x$ and $y$. To see that there is exactly one such merge-inversion, observe that after any call of MERGE that involves both $x$ and $y$, they are in the same sorted subarray and will therefore both appear in $L$ or both appear in $R$ in any given call thereafter. Thus, we have proven the claim.
By the way, $L$ and $R$ are arrays. Could someone please explain why there's exactly one merge-inversion? For example, $L$ is $[1, 3, 5, 7]$ and $R$ is $[2, 4, 6, 8]$ there are 6 inversions. Why does the author say about exactly one?
I will add any details if something is not clear.