| 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 (Journal article) |
| BibLATEX: | @report{KP1992aR,
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},
}
|