#
Sorting and Selection with Equality Comparisons

##
Will Devanny

Abstract:
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 = otherwise. We determine
the complexity of sorting (finding the frequency of every element), finding
mode and other frequently occurring elements using only =,= comparisons. We
show that Ω(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 Θ(n log(n/m)) bound in the model where comparisons
are <, =, > or ≤, >.

Paper by Varunkumar Jayapul, J. Ian Munro, Venkatesh Raman, Srinivasa Rao
Satti