Sorting binary array - Array containing only 0 and 1 in one pass OR two color sort

Problem

Sort a binary array - array containing 0s and 1s in 1 pass. This is also called two color sort.

Example

Input - Binary unsorted array
A = {0,1,1,0,0,1};

Output - binary sorted array
B = {0,0,0,1,1,1}

Solution

This is similar to quicksort partition algorithm. Though normal sorting takes O(n log n) time, but we have to just partition 0 from 1, and hence it should only take time of partitioning - O(n). Lets see how?

We take low at index 0 of array, high at the of the array. Now we will follow this pseudocode:

Pseudocode:

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

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

c implementation

int main()
{
 int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};
 int N = 18;
 int *low, *high;

 low = arr;//low points to start of arr
 high = arr + N;//high points to end of arr
 while(low <= high)
 {
  while( (low < high) && (*low == 0) )
   low ++;

  while( (low < high) && (*high== 1) )
   high--;

  if( low < high)
  {
   int temp = *low ;
   *low = *high;
   *high = temp;
   low ++;
   high--;
  }
 }
 for(int i=0;i<N;i++)
  printf("%d ",arr[i]);

 return 0;
}

Time complexity:
Since we have to examine each of n input elements, we can't improve on O(n). Also, since the algorithm requires O(1) memory, you can't improve on that either (there's nothing asymptotically better than O(1)).

But it is still better than comparison sorts like quicksort, merge sort. Though the below pseudocode will look like partition method in quicksort, which was also O(n) algorithm.


Thanks.