Как отсортировать целочисленный массив на отрицательные, нулевые и положительные части без изменения относительного положения?

Приведите алгоритм O (n), который принимает на вход массив S, затем делит S на три набора: отрицательные, нулевые и положительные. Покажите, как это реализовать на месте, то есть без выделения новой памяти. И вы должны соблюдать относительную последовательность чисел. например: {-1, 4, 0, -2, 1, 2} ==> {-1, -2, 0, 4, 1, 2}

Я не уверен, завершится ли такое решение. Лучшие решения, которые я могу придумать, следующие:

Решение 1. Используя дополнительный массив целых чисел, затем обойдите весь массив, чтобы получить отрицательные значения, затем нули, затем положительные.

Решение 2: Не сохраняйте относительную последовательность чисел. Затем дважды зациклите массив:

    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++]);  
    }  
}