Sorting multisets stably in minimum space
Authors:Jyrki Katajainen and Tomi Pasanen
Published in:Acta Informatica 31,4 (1994), 301-313
Full text:<pdf.gif>PDF (177 kB)  <ps.gif>PS (340 kB)  
Abstract:In a decision tree model, Ω(n log2 n − ∑i=1m ni log2 ni + 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 ni 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 A0 and A1. The problem is to recover A from its constituents A0 and A1. The information available is the partitioning element used and a bit array of size n indicating whether an element of A0 or A1 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.

Related:<html.gif>HTML (Conference paper)  
  author = {Jyrki Katajainen and Tomi Pasanen},
  title = {Sorting multisets stably in minimum space},
  journaltitle = {Acta Informatica},
  volume = {31},
  number = {4},
  year = {1994},
  pages = {301--313},
This page was generated by Jyrki Katajainen <> on 31.12.2011.