# 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. <, =, >? (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)$.
• I mostly agree with you; however I'm interested in some graphical representation of such a ternary tree. Say n=3, it's not clear to me what the children of the node a1==a2 should be. Depending on the representation, internal nodes could have less than 3 children Oct 2, 2016 at 22:36