TAOCP 5.2.4 Exercise 21

We modify Algorithm L (List merge sort) as follows.

taocpmathematicsalgorithmsvolume-3medium

Section 5.2.4: Sorting by Merging

Exercise 21. [22] (A. J. Smith.) Explain how to extend Algorithm L so that, in addition to sorting, it computes the number of inversions present in the input permutation.

Verified: no
Solve time: 4m06s

Solution

We modify Algorithm L (List merge sort) as follows. The algorithm uses a linked list with a dummy header node 0; LINK(i) points to the next record, and K_i is the key of record i. The steps are referred to by their labels in the book (L1, L2, …).

  1. Initialize inversion counter. In step L1, after LINK(0) ← 1, set INV ← 0.
  2. Compute length of first run. In step L3, when the first run Q … R is identified, also count its length. Replace the loop
    Set R ← Q. While LINK(R) ≠ 0 and K_R ≤ K_{LINK(R)} do R ← LINK(R).
    with
    Set R ← Q, LEN ← 1. While LINK(R) ≠ 0 and K_R ≤ K_{LINK(R)} do R ← LINK(R), LEN ← LEN + 1.
  3. Initialize remaining counter for merge. In step L5, after U ← Q, V ← S, set REM ← LEN.
  4. Count inversions when taking from second run. In step L7, after the three assignments
    Set LINK(P) ← V, P ← V, V ← LINK(V)
    insert the statement INV ← INV + REM.
  5. Decrement remaining counter when taking from first run. In step L8, after the three assignments
    Set LINK(P) ← U, P ← U, U ← LINK(U)
    insert the statement REM ← REM - 1.

All other steps remain unchanged. When the algorithm terminates, INV contains the number of inversions in the original permutation.

Proof of correctness. We show by induction on the sequence of merges that INV always equals the number of inversions between elements that currently belong to different runs. Initially, the list is partitioned into maximal ascending runs. Since each run is sorted, it contains no inversions; all inversions of the permutation are between different runs. Thus the invariant holds initially with INV = 0.

Consider a merge of two sorted runs A (first run) and B (second run). Let a_1, …, a_m be the elements of A in order, and b_1, …, b_n the elements of B. During the merge, elements are output in sorted order. Whenever an element b_j is chosen before the remaining elements of A, it is smaller than all those remaining elements. Because A precedes B in the current list, each such pair (a_i, b_j) with a_i > b_j is an inversion in the original permutation. At the moment b_j is taken, the number of remaining elements in A is exactly REM. Adding REM to INV accounts for these cross inversions. No other inversions are created or destroyed by the merge, because the relative order within A and within B is preserved, and the new merged run is sorted (hence contains no internal inversions). Therefore the invariant is maintained.

When the algorithm finishes, there is only one run, so there are no inversions between different runs. By the invariant, INV equals the total number of inversions in the original permutation. ∎

This completes the proof.