Sorting and Searching in Multisets

In this paper the problem of sorting multisets is considered. An information theoretic lower bound on the number of three branch comparisons is obtained, and it is shown that this bound is asymptotically attainable. It is shown that the multiplicities of a set can only be obtained by comparisons if the total order is discovered in the process. A lower bound on finding the mode of a multiset as a function of the actual multiplicity is given, and it is demonstrated that the bound can be achieved to within a multiplicative constant. The determination of the intersection of two multisets is also discussed, and partial results, including a generalization of Reingold’s result for determining whether or not two sets have a nonempty intersection, are obtained.