Quem poderia responder

Cada posição do vetor contém um valor que é ou 0 ou 1?
Cara, mesmo assim, eu acho que a complexidade, no pior caso, fica um pouco menos de O(n^2) (percorrer até encontrar o primeiro 1, e depois percorrer a partir do 1 até encontrar um 0 e trocar os valores).

Eu desconheço.

Não sei se você estaria “cheatando”, mas você poderia contar a quantidade de 0s e 1s com complexidade O(n). Depois pegar a lista e preencher com os respectivos valores de 0s e 1s, resultando em O(n) novamente. Mas isso não é um algoritmo de ordenação (eu acho).

Abraço.

É verdade, mas como justificar ser possivel criar esse vetor de n posições com valores 0 e 1, de forma teorica?

O algoritmo é muito simples e é de ordem O(N) mesmo.
Basta ver que você deve contar a quantidade de valores 0 e 1 que deve ter o vetor ordenado, que é a mesma quantidade de valores 0 e 1 do vetor original. Então basta contar quantos valores 0 e 1 existem no vetor original, o que é uma operação de ordem O(N).