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.

@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},
}