Let's define: $ a_i:a_j \Longleftrightarrow a_i < a_j;\ a_i=a_j;\ a_i > a_j $
So it is similiar to normal operation $<$, but $:$ give information when elements are equal.
I want show that lower bound for sort array of $n$ elements with this operation is $\Omega (n\log n)$.
I know proof for normal comparison. Nevertheless I can't solve it, I thought about it a long time, but without effect. Can you help me ?
(It isn't homework, nowadays I am on holiday :))