Рассмотрим следующую проблему.

Нам дан массив элементов, принадлежащих одному из двух классов: либо красный, либо синий. Мы должны переставить элементы массива так, чтобы все синие элементы были первыми (а все красные элементы следовали). Перестановка должна быть сделана стабильным способом, это означает, что относительный порядок синих элементов должен быть сохранен (то же самое для красных).

Есть ли умный алгоритм, который бы выполнял вышеуказанную перестановку на месте?

Решение не на месте, конечно, просто.

Очевидным решением на месте было бы применить любой устойчивый алгоритм сортировки к массиву. Однако использование полноценного алгоритма сортировки в массиве интуитивно кажется избыточным, особенно учитывая тот факт, что мы имеем дело только с двумя классами элементов.

Любые идеи с благодарностью.