highly optimized algo to sort an array consisting of only 0s n 1s
algorithm, sorting
Solution
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)`).
Problem
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.