TAOCP 5.2.1 Exercise 1

Exercise 1. [**] [10] Is Algorithm S a stable sorting algorithm?

Verified: no
Solve time: 13m25s

Yes. Algorithm S is stable.

Assume that two records $R_p$ and $R_q$ have equal keys, with $p<q$. When $R_q$ is inserted into the already sorted portion of the file, step S4 compares its key $K$ with preceding keys. The algorithm moves a record only when $K<K_i$. If $K=K_i$, the test in step S4 succeeds and the algorithm proceeds directly to step S5, inserting $R_q$ immediately to the right of the existing record having the same key.

Therefore a later record with key value $K$ can never pass in front of an earlier record with the same key. Since the only changes in relative order arise from these insertion operations, the relative order of equal-key records is preserved throughout the sort.

Hence Algorithm S is a stable sorting algorithm.

$$ \boxed{\text{Algorithm S is stable.}} $$