highly optimized algo to sort an array consisting of only 0s n 1s

Question

I need to find a highly optimized algo to sort an array consisting of only 0s n 1s.

My version of the solution is to count the no. of zeroes(say x) and ones(say y). Once you do that, place x zeroes in the array followed by y 1s. This makes it O(n).

Any algo that runs better than this??? I was asked this question in interview.

Answer 1

Since you have to examine each of n input elements, you can't improve on O(n).

Also, since your algorithm requires O(1) memory, you can't improve on that either (there's nothing asymptotically better than O(1)).

Answer 2

we can't do better than O(n), but looks like we can do in one pass

low = 0; 
high = arr.length - 1;

while (low < high) {
    while (arr[low] == 0) {
        low ++;
    }
    while (arr[high] == 1) {
        high --;
    }
    if (low < high) {
    //swap arr[low], arr[high]
    }
}