| Stable minimum space partitioning in linear time | |
| Authors: | Jyrki Katajainen and Tomi Pasanen |
| Published in: | BIT 32,4 (1992), 580-585 |
| Full text: |  PDF (269 kB) |
| DOI: | 10.1007/BF01994842 |
| 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 (Technical report) HTML (Errata) |
| BibLATEX: | @article{KP1992bJ,
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},
}
|