How to sort an integer array into negative, zero, positive part without changing relative position?

Question

Give an O(n) algorithm which takes as input an array S, then divides S into three sets: negatives, zeros, and positives. Show how to implement this in place, that is, without allocating new memory. And you have to keep the number's relative sequence. for example: {-1, 4, 0, -2, 1, 2} ==> {-1, -2, 0, 4, 1, 2}

I am not sure whether or not such an solution exits. The best solutions I can think out are:

Solution 1: Using an extra integer array, then traverse the whole array to get negatives, then 0s, then positives.

Solution 2: Do not keep number's relative sequence. Then loop the array two times:

    template <typename Type>  
void Partion(Type *array, int begin, int end, Type v, int &l, int &r) 
{  
    l = begin;  
    for (int i=begin; i!=end; ++i)  
    {  
        if (array[i] < v)  
            swap(array[i], array[l++]);  
    }  
    r = l;  
    for (int j=l; j!=end; ++j)  
    {  
        if (array[j] == v)  
            swap(array[j], array[r++]);  
    }  
} 

Answer 1

This is an instance of the Dutch national flag problem studied by Edsger Dijkstra. It's interesting in that no stable solution to this problem is known that runs in O(n) time and O(1) space (or at least, the last time I checked the literature, no known solution to the problem exists).

Answer 2

I'm not sure if this helps, but the requirement to stably partition into three classes can be reduced to the problem of stably partitioning into two classes: separate the negative from non-negative, then the positive from non-positive. If the two-class problem can be solved in O(1) space and O(n) time, the solution can be applied twice to solve the original problem.