Sorting multisets and vectors in-place

An optimal in-place algorithm to lexicographically sort an array of multidimensional vectors is obtained, by applying the multiset sorting algorithm in each coordinate by adapting heapsort for multisets.

Abstract

When a list to be sorted consists of many repeated elements (i.e. when it is a multiset), the familiar Ω(n lg n) lower bound on the number of comparisons is replaced by a bound that depends on the multiplicities of the elements in the list. We adapt heapsort for multisets and provide the first in-place algorithm for multisets that achieves the optimal bound up to lower order terms. We, then, obtain an optimal in-place algorithm to lexicographically sort an array of multidimensional vectors, by applying the multiset sorting algorithm in each coordinate. We exploit the relationship between the two sorting problems to improve the lower order term of a known lower bound[2] for sorting multisets. It follows that the ("non in-place") algorithms developed by Munro and Spira [8] for multisets are within O(n) time optimal. Our improvement to the lower bound for sorting multisets also improves a lower bound (in the lower order term) for determining the mode, the most frequently occurring element in the multiset.