How to make a stable sort of binary values in linear time?

How to make a stable sort of binary values in linear time?

Let us suppose that we have a:
class Widget;
std::vector<Widget>;
And we have a function:
bool belongsToLeft(Widget w);
I would like to sort the container according to this predicate. So far I
though up this algorithm. It progresses from both ends of the range. Once
it finds a pair of values that simultaneously belong to the other end, it
swaps them.
template <typename TIterator, typename TPredicate>
TIterator separate(TIterator begin, TIterator end, TPredicate belongsLeft)
{
while (true)
{
while (begin != end && belongsLeft(*begin))
++begin;
while (begin != end && !belongsLeft(*end))
--end;
if (begin == end)
return begin;
std::swap(*begin, *end);
}
}
The problem is that this algorithm is not stable:
#include <vector>
#include <iostream>
int main()
{
std::vector<int> numbers = {6, 5, 4, 3, 2, 1};
separate(numbers.begin(), numbers.end(), [](int x){return x%2 == 0;});
for (int x : numbers)
std::cout << x << std::endl;
return 0;
}
outputs:
6
2
4
3
5
1
How can I modify this algorithm to be stable and keep the linear time?