Q. Given a binary array of 0 and 1, you have to sort it such that all 0s lie on left side followed by all 1. The sorting should not use any external data structure.

A. The best approach is to use a quick sort kind of algorithm. Here, its only 0s and 1s hence, sorting will happen in O(n) time as we don’t need to call it recursively.

- Maintain two pointers left and right.
- Start traversing left pointer towards right until 1 is encountered.
- Start right pointer towards left until 0 is encountered.
- Swap elements at both pointers.
- Continue doing so until left and right pointer converge.

Since, we have to traverse the array only once, sorting happened in O(n) time.

### Like this:

Like Loading...

*Related*

Hi, very well explained. Here is my link as well:

http://k2code.blogspot.in/2010/04/sorting-binary-array.html with the same partition logic.