number of comparison in sort algorith with special operation
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.