Short Note: Finding a majority when sorting is not available
D. Campbell · The Computer Journal · 1991
Let the abstract data type Object support an equivalence relation. This paper contains a fast, simple, space-frugal algorithm to determine whether a majority of an arbitrary set of such Objects belong to the same equivalence class (are the ‘same’) even when no total order is available for sorting and even if there are infinitely many different equivalence classes.