Parallel Equivalence Class Sorting: Algorithms, Lower Bounds, and Distribution-Based Analysis

William E. Devanny, Michael T. Goodrich, Kristopher Jetviroj

We study parallel comparison-based algorithms for finding all equivalence classes of a set of $n$ elements, where sorting according to some total order is not possible. Such scenar…