Имеется массив из n объектов. У объектов есть ключ, принимающих два значения: 0 или 1.
Надо придумать максимально эффективный алгоритм, который выполняет стабильную сортировку массива по ключу.
Объём дополнительно используемой памяти должен быть O(1).

Задача наверняка известная и изученная. Фактически, надо реализовать stable_partition из STL с ограничением на объём дополнительной памяти. Лучший алгоритм, который я смог придумать, в худшем случае имеет сложность O(n*log(n)). Можно ли как-то быстрее? Если нельзя, то почему?