TAOCP 5.2.2 Exercise 13

Section 5.2.2: Sorting by Exchanging

Exercise 13. [10] Is Batcher's method a stable sorting algorithm?

Verified: no
Solve time: 4m16s

Yes, Batcher's merge exchange sort is stable. Every compare-exchange operation in the algorithm is defined to swap two records only when their keys are in strictly decreasing order (i.e., (K_i > K_j)). Equal keys are therefore never interchanged directly. Moreover, because all operations are of this form, two equal keys can never cross each other indirectly: any sequence of such stable comparators preserves the original relative order of equal elements. Hence the algorithm is stable. ∎