TAOCP 5.3.1 Exercise 2
The root node compares $K_1$ and $K_2$.
Section 5.3.1: Minimum-Comparison Sorting
Exercise 2. [**] [16] When keys can be equal, each comparison may have three results instead of two: $K_i < K_j$, $K_i = K_j$, $K_i > K_j$. Sorting algorithms for this general situation can be represented as extended ternary trees, in which each internal node $v$ has three subtrees; the left, middle, and right subtrees correspond respectively to the three possible outcomes of the comparison.
Draw an extended ternary tree that defines a sorting algorithm for $n = 3$, when equal keys are allowed. There should be 13 external nodes, corresponding to the 13 possible outcomes listed in exercise 3.
Verified: yes
Solve time: 1m12s
The root node compares $K_1$ and $K_2$.
If $K_1 = K_2$, the next comparison is $K_2 : K_3$. When $K_2 < K_3$, the ordering is $K_1 = K_2 < K_3$. When $K_2 = K_3$, the ordering is $K_1 = K_2 = K_3$. When $K_2 > K_3$, the ordering is $K_3 < K_1 = K_2$. This subtree has exactly three external nodes, corresponding to these three outcomes.
If $K_1 < K_2$, the next comparison is $K_2 : K_3$. When $K_2 < K_3$, the ordering is $K_1 < K_2 < K_3$. When $K_2 = K_3$, the ordering is $K_1 < K_2 = K_3$. When $K_2 > K_3$, a further comparison $K_1 : K_3$ is made. If $K_1 < K_3$, the ordering is $K_1 < K_3 < K_2$. If $K_1 = K_3$, the ordering is $K_1 = K_3 < K_2$. If $K_1 > K_3$, the ordering is $K_3 < K_1 < K_2$. This branch therefore produces five external nodes.
If $K_1 > K_2$, the construction is symmetric to the case $K_1 < K_2$. The next comparison is $K_1 : K_3$. When $K_1 < K_3$, the ordering is $K_2 < K_1 < K_3$. When $K_1 = K_3$, the ordering is $K_2 < K_1 = K_3$. When $K_1 > K_3$, a further comparison $K_2 : K_3$ is made, yielding $K_2 < K_3 < K_1$, $K_2 = K_3 < K_1$, and $K_3 < K_2 < K_1$. This branch also produces five external nodes.
The three branches together account for $3 + 5 + 5 = 13$ external nodes, corresponding exactly to all weak orderings of three elements with equality allowed. This completes the construction of the extended ternary sorting tree. ∎