How to partition bits in a bit array with less than linear time
<p>This is an interview question I faced recently.</p>

<hr>

<p>Given an array of 1 and 0, find a way to partition the bits <code>in place</code> so that 0's are grouped together, and 1's are grouped together. It does not matter whether 1's are ahead of 0's or 0's are ahead of 1's.</p>

<p>An example input is <code>101010101</code>, and output is either <code>111110000</code> or <code>000011111</code>.</p>

<p>Solve the problem in less than linear time.</p>

<p>Make the problem simpler. The input is an integer array, with each element either 1 or 0. Output is the same integer array with integers partitioned well.</p>

<hr>

<p>To me, this is an easy question if it can be solved in <strong>O</strong>(N). My approach is to use two pointers, starting from both ends of the array. Increases and decreases each pointer; if it does not point to the correct integer, swap the two.</p>

<pre>
    int * start = array;
    int * end = array + length - 1;

    while (start &lt end) {
        // Assume 0 always at the end
        if (*end == 0) {
            --end; 
            continue;
        }

        // Assume 1 always at the beginning
        if (*start == 1) {
            ++start; 
            continue;
        }

        swap(*start, *end);
    }
</pre>

<p>However, the interview insists there is a sub-linear solution. This makes me thinking hard but still not get an answer.</p>

<p>Can anyone help on this interview question?</p>

<p><strong>UPDATE</strong>: Seeing replies in SO stating that the problem cannot be solved in sub-linear time, I can confirm my original idea that there cannot be a solution of sub-linear. </p>

<p>Is it possible the interviewer plays a trick?</p>
