number of comparison in sort algorith with special operation Let's define: $ a_i:a_j \Longleftrightarrow  a_i &lt; a_j;\ a_i=a_j;\ a_i &gt; a_j $
So it is similiar to normal operation $&lt;$, 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 :))
Let's suppose that it is possible to sort it with $:$ in time $o(nlogn$).
So we use ordinary comparisons: $&lt;$ and $&gt;$. If both $a_i&lt;a_j $ and $a_j &gt; a_i$ is not truth then we conclude $a_i=a_j$.  And now, we can sort in time:
$o(2nlogn)=o(nlogn)$ - it is impossible.