I hope the following approach will work. Let 'a' be the input array with size n.
int i = 0, j = 1; while( true) { while( i < n && a[i] == 0) i += 2; while( j < n && a[j] == 1) j += 2; if ( i < n && j < n ) swap(a[i], a[j]); if ( i > n && j < n ) { do single pass 2-color sort only on odd indices from j to n-1 putting 1's before 0's; break; } if ( i < n && j > n ) { do single pass 2-color sort only on even indices from i to n-1 putting 0's before 1's; break; } } Every element of the array is touched exactly once and it is in place. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.