Sorting and Selection with Equality Comparisons

We consider the fundamental sorting and selection problems on a list of elements that are not necessarily from a totally ordered set. Here relation between elements are determined by ‘equality’ comparisons whose outcome is \(=\) when the two elements being compared are equal and \(\ne \) otherwise. We determine the complexity of sorting (finding the frequency of every element), finding mode and other frequently occurring elements using only \(=, \ne \) comparisons. We show that \(\Omega (n^2/m)\) comparisons are necessary and this many comparisons are sufficient to find an element that appears at least m times. This is in sharp contrast to the bound of \(\Theta (n \log (n /m))\) bound in the model where comparisons are \( \) or \(\le , >\).