TAOCP 5.2.2 Exercise 7
Batcher’s merge-exchange method is not stable.
Section 5.2.2: Sorting by Exchanging
Exercise 7. [**] [10] Is Batcher’s method a stable sorting algorithm?
Verified: no
Solve time: 2m53s
Batcher’s merge-exchange method is not stable. The algorithm repeatedly compares and exchanges elements according to a fixed pattern that depends only on their positions, not on their original order within equal keys. During a merge-exchange step, two equal keys from different halves of a subsequence may be swapped because the comparison criterion considers only their relative positions in the current subsequence. Consequently, the original relative order of equal keys can be altered, violating the definition of stability. This completes the proof.
∎