Sorting multisets stably in minimum space (Q1338888)

We consider the problem of sorting a multiset of size \(n\) containing \(m\) distinct elements, where the \(i\)th distinct element appears \(n_ i\) times. Under the assumption that our model of computation allows only the operations of comparing elements and moving elements in the memory, \(\Omega (n \log n - \sum^ m_{i=1} n_ i \log n_ i + n)\) is known to be a lower bound for the computational complexity of the sorting problem. In this paper we present a minimum space algorithm that sorts stably a multiset in asymptotically optimal worst-case time. A Quicksort type approach is used, where at each recursive step the median is chosen as the partitioning element. To obtain a stable minimum space implementation, we develop linear-time in-place algorithms for the following problems, which have interest of their own: Stable unpartitioning: Assume that an \(n\)-element array \(A\) is stably partitioned into two subarrays \(A_ 0\) and \(A_ 1\). The problem is to recover \(A\) from its constituents \(A_ 0\) and \(A_ 1\). The information available is the partitioning element used and a bit array of size \(n\) indicating whether an element of \(A_ 0\) or \(A_ 1\) was originally in the corresponding position of \(A\). Stable selection: The task is to find the \(k\)th smallest element in a multiset of \(n\) elements such that the relative order of identical elements is retained.