Sorting binary array in linear time

example – A = [1,0,0,0,1,1,1,0,0,0]

Output – [0,0,0,0,0,0,1,1,1,1]

Approaches

1. Count no. of 0s and 1s and place them that number of times in the array.
2. Instead of counting number of 0s, if the current element is 0, we can place 0 at next available position (maintain a pointer) in the array. After all elements in the array are processed, we fill all remaining indices by 1.
3. Partitioning approach of Quick Sort Algorithm – We can mark the pivot as 1 and each time we encounter 1 it is swapped with a 0. So in one pass our array will be sorted.