Stable minimum space partitioning in linear time
Authors:Jyrki Katajainen and Tomi Pasanen
Published in:BIT 32,4 (1992), 580-585
Full text:<pdf.gif>PDF (269 kB)  
Copyright:© Springer
Abstract:In the stable 0-1 sorting problem the task is to sort an array of n elements with two distinct values such that equal elements retain their relative input order. Recently, Munro, Raman and Salowe gave an algorithm which solves this problem in O(n log* n) time and constant extra space. We show that by a modification of their method the stable 0-1 sorting is possible in O(n) time and O(1) extra space. Stable three-way partitioning can be reduced to stable 0-1 sorting. This immediately yields a stable minimum space quicksort, which sorts multisets in asymptotically optimal time with high probability.
Related:<html.gif>HTML (Technical report)  <html.gif>HTML (Errata)  
  author = {Jyrki Katajainen and Tomi Pasanen},
  title = {Stable minimum space partitioning in linear time},
  journaltitle = {BIT},
  volume = {32},
  number = {4},
  year = {1992},
  pages = {580--585},
This page was generated by Jyrki Katajainen <> on 31.08.2014.