4.27

1. O(n) reversals always suffice
Scan the permutation from left to right. For position i (1-based) let j be the current index that contains the value i. If j>i do one operation reverse(p,i,j); this places i in its final spot. Because the cursor i increases after every step, each value is fixed once and we perform at most n-1 = O(n) reversals.

2. Sorting with total cost O(n log² n)
We adopt a divide–and–conquer (merge–sort) scheme and use block rotations (three consecutive reversals) to merge two already sorted halves. A rotation of the form

reverse(p, a, b) reverse(p, b+1, c) reverse(p, a, c)

moves the left block [a..b] to the right of [b+1..c] at cost c-a+1.

Merge procedure

merge(p, l, m, r): # p[l..m] and p[m+1..r] are increasing i ← l while i ≤ m and p[i] ≤ p[m+1]: i ← i+1 # skip elements already in place if i > m: return # halves are already ordered j ← m+1 while i ≤ m: # smallest element in the right half that is > p[i] k ← lower_bound(p, j, r, p[i]) # binary search rotate(p, i, j-1, k-1) # three reversals shift ← k-j i ← i + shift + 1 m ← m + shift j ← k

Main algorithm

sort(p, l, r): if l < r: m = ⌊(l+r)/2⌋ sort(p, l, m) sort(p, m+1, r) merge(p, l, m, r)

Cost analysis
During one call merge(p,l,m,r) we perform a sequence of rotations. For every rotation we locate k with binary search, so the number of comparisons per moved element is O(log |segment|). Each rotation touches every element in the merged interval once, hence its cost is proportional to the segment length. Therefore
    cost(merge of size h) = O(h log h).
The recurrence for the total cost is
    C(n) = 2·C(n/2) + O(n log n).
Solving it yields C(n) = O(n log² n). All auxiliary work (binary searches, index updates) takes only O(log n) per element, so the running time is the same order.

Correctness proof (sketch)
Induction on the size of the interval. Base case (|interval| ≤ 1) is trivially sorted. Inductive step: by hypothesis both halves become sorted after the recursive calls; the merge routine preserves order because 1. it always moves a contiguous block of the right half that is smaller than the next left element in front of that element, and 2. rotations keep the internal order of each block. Thus the whole interval is correctly sorted, completing the proof.

Hence every permutation can be sorted with at most O(n) reversals, and with the length-weighted metric the above algorithm achieves total cost O(n log² n).

Back to Chapter 4