Stable minimum space partitioning in linear time
Authors:Jyrki Katajainen and Tomi Pasanen
Publication:Report 92/4, Department of Computer Science, University of Copenhagen (1992), 9 pp.
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 [BIT 1990] 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 (Journal article)  
  author = {Jyrki Katajainen and Tomi Pasanen},
  title = {Stable minimum space partitioning in linear time},
  type = {Report},
  number = {92/4},
  institution = {Department of Computer Science, University of Copenhagen},
  year = {1992},
  pagetotal = {9},
This page was generated by Jyrki Katajainen <> on 31.08.2014.