In a decision tree model, Ω(n log_{2}n − ∑_{i=1}^{m}n_{i}
log_{2}n_{i} + n) is known to be a lower bound for sorting a
multiset of size n containing m distinct elements, where the ith
distinct element appears n_{i} times. 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 implemention, 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 kth
smallest element in a multiset
of n elements such that the relative order
of identical elements is retained.