Stable partition3 implementation

[Nick B via Digitalmars-d]

On Friday, 10 July 2015 at 00:39:16 UTC, Xinok wrote:
> On Thursday, 9 July 2015 at 21:57:39 UTC, Xinok wrote:
>> I found this paper which describes an in-place algorithm with 
>> O(n) time complexity but it's over my head at the moment.
>>
[snip]
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.5554&rep=rep1&type=pdf

from the pdf, above, in case readers, like me, don't know the 
context of a Stable Partition implementation:

Stable minimum space partitioning
in linear time
Jyrki Katajainen1 and Tomi Pasanen2

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(nlog*n)
3 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.
CR categories: E.5, F.2.2.

The stable 0-1 sorting problem is defined as follows: Given an 
array of n elements
and a function f mapping each element to the set {0,1}, the task 
is to rearrange the
elements such that all elements, whose f-value is zero, become 
before elements, whose
f-value is one. Moreover, the relative order of elements with 
equal f-values should be
maintained. For the sake of simplicity, we hereafter refer to 
bits instead of the f-values
of elements.

Stable partitioning is a special case of stable 0-1 sorting, 
where the f-values are
obtained by comparing every element xi
to some pivot element xj  (which will not take part in 
partitioning):