TAOCP 5.2.4 Exercise 5

Exercise 5. [21] [21] Is Algorithm L a stable sorting method?

Verified: yes
Solve time: 1m15s

Solution

A sorting method is stable if whenever two records $R_a$ and $R_b$ satisfy $K_a = K_b$ and $R_a$ precedes $R_b$ in the input, then $R_a$ precedes $R_b$ in the output.

Algorithm L (straight insertion sorting as defined in Section 5.2.1) processes the records in order $R_1,\ldots,R_N$. Assume after $j-1$ steps the prefix $R_1,\ldots,R_{j-1}$ is sorted. At step $j$, the algorithm removes $R_j$ and inserts it into its correct position among $R_1,\ldots,R_{j-1}$ by scanning leftward until it finds the first position $i$ such that $K_i \le K_j$, and then placing $R_j$ in position $i+1$, shifting all elements $R_{i+1},\ldots,R_{j-1}$ one position to the right.

Consider two records $R_a$ and $R_b$ with $a < b$ and $K_a = K_b$. When $R_b$ is processed, the prefix $R_1,\ldots,R_{b-1}$ already contains $R_a$, and all elements are arranged so that equal keys appear contiguously in the region containing $R_a$. During insertion of $R_b$, the scan moves left past any record $R_t$ with $K_t > K_b$, but it does not move past records with $K_t = K_b$, since the stopping condition is $K_i \le K_b$. Hence the final position chosen for $R_b$ is immediately to the right of the last record in the prefix whose key equals $K_b$, which includes $R_a$.

Therefore $R_b$ is placed after all previously existing records with key $K_b$, in particular after $R_a$, so the relative order of equal keys is preserved throughout all insertions.

This completes the proof. ∎