Selected Solutions for Chapter 2: Getting Started 2-3
d. We follow the hint and modify merge sort to count the number of inversions in
‚.n lgn/ time.
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 C 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 D AŒi and y D 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. More-
over, 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, ob-
serve 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.
We have shown that every inversion implies one merge-inversion. In fact, the
correspondence between inversions and merge-inversions is one-to-one. Sup-
pose we have a merge-inversion involving values x and y, where x originally
was AŒi and y was originally AŒj . Since we have a merge-inversion, x > y.
And since x is in L and y is in R, x must be within a subarray preceding the
subarray containing y. Therefore x started out in a position i preceding y’s
original position j , and so .i; j / is an inversion.
Having shown a one-to-one correspondence between inversions and merge-
inversions, it suffices for us to count merge-inversions.
Consider a merge-inversion involving y in R. Let ´ be the smallest value in L
that is greater than y. At some point during the merging process, ´ and y will
be the “exposed” values in L and R, i.e., we will have ´ D LŒi and y D RŒj
in line 13 of MERGE. At that time, there will be merge-inversions involving y
and LŒi; LŒi C 1; LŒi C 2; : : : ; LŒn
1
, and these n
1
i C 1 merge-inversions
will be the only ones involving y. Therefore, we need to detect the first time
that ´ and y become exposed during the MERGE procedure and add the value
of n
1
i C 1 at that time to our total count of merge-inversions.
The following pseudocode, modeled on merge sort, works as we have just de-
scribed. It also sorts the array A.
COUNT-INVERSIONS.A; p; r/
inersions D 0
if p < r
q D b.p C r/=2c
inersions D inersions C COUNT-INVERSIONS.A ; p; q/
inersions D inersions C COUNT-INVERSIONS.A ; q C 1; r/
inersions D inersions C MERGE-INVERSIONS.A; p; q; r/
return inersions
