Ternary decision tree for the lower bound of comparison sort with 3-way comparisons All the proofs I've seen about the Ω(nlgn) lower-bound for comparison sorts use binary decision tress like this (from CLRS textbook)


Now what if each comparison yields strictly 3 outcomes, i.e. &lt;, =, &gt;? (the input array is allowed to contain repeated elements)

The bound is probably still Ω(nlgn), but I'm not sure how one would draw the (not necessarily full) ternary decision tree (still with unique leaf nodes); this kind of tree is mentioned in the proof of the water jug problem.
The proof would be exactly the same, using a ternary tree (where each internal node has three children) instead of a binary tree. A ternary tree of depth $d$ has at most $O(3^d)$ notes, so a sorting tree would have to satisfy $n! = O(3^d)$, which implies that $d = \Omega(n\log n)$.