TAOCP 5.2.2 Exercise 3
Yes, Algorithm B is a stable sorting algorithm.
Section 5.2.2: Sorting by Exchanging
Exercise 3. [**] [10] Is the bubble sort Algorithm B a stable sorting algorithm?
Verified: yes
Solve time: 1m42s
Yes, Algorithm B is a stable sorting algorithm. Stability requires that if two records have equal keys, their relative order in the input is preserved in the output. In Algorithm B, the only exchanges occur when K_j > K_{j+1} in step B3. If K_j = K_{j+1}, no exchange is performed, so records with equal keys are never reordered relative to each other. Consequently, the original order of equal keys is maintained throughout all passes of the bubble sort.
This completes the proof.
∎