## Inspiration

Alexander Stepanov and Paul McJones in the their book “Elements of Programming” (Chaper 11.1) describe a stable partition algorithm that appears to be more complex than necessary. Here I present an improvement.

## Problem

Definition A partition of sequence with respect to a predicate P is a permutation of the sequence such that all elements satisfying the predicate appear before any element that does not or vice versa.

If x and y are two elements in the original sequence then a stable partition is one where `P(x) = P(y)` implies that x appears before y in the partitioned sequence if and only if x appears before y in the original sequence.

A semi stable partition is a partition that is stable only for P(x) = P(y)= false.

The following C++ function generates an in-place semi stable partition. Notice that using the C++ convention last points to one past the last element of the array.while first points to first element of the array.

```template<class Iter,class Pred>
Iter stable_part(Iter first, Iter last, Pred P) {
Iter i = first;
Iter p = first;

// let [first',last') refer to the unmodified data
// Invariant
// [first,i) is semi-stable partitioned at p.
//  In other words
// (1) x in [first,p)  => !P(x)
// (2) x in [p,i) => P(x)
// (3) [first,i) is a permutation of
//       [first', first' +(i-first))
// (4)  x,y in [first,p) &
//      x precedes y in [first,p) =>
//      x precedes y in [first',first' +(i-first))
while(i!=last) {
if( P(*i))
++i;
else {
swap(*i,*p); ++i;++p;
}
}
return p;
}
```

## Proof

Notice that the invariant is trivially established at the beginning of the loop. The `if `statement extends the sequence that is semi stable partitioned. Hence the loop invariant holds at the end of the `if `statement. Hence on termination of the loop `p` is a point of semi stable partition of the whole sequence. 