algorithm - Arrange 0's & 1's in a array

Question

This is one of an interview question which I had recently. I would like to know others perception of approach for this problem.

Question:

You are given a structure which holds employee details with two elements, int department and string name.

struct Employee
{ 
    string Name;
    int Dept;
}

You are given details of N Employees, among which N/2 employees have Dept == 0 and N/2 employees have Dept == 1, arranged in some arbitrary order. You need to sort the employee details based on their Dept value and it should be stable i.e., the order of 1s and 0s in the original record should be maintained.

For example, given the following sample data:

Name         Dept

X1           0
X2           1
X3           0
X4           1
X5           0

after sorting the result should be:

Name         Dept

X2           1
X4           1
X1           0
X3           0
X5           0

The algorithm should be stable and the time complexity should be O(N), with constant space for additional variables (which means sorting should be done in-place).

Answer 1

Allocate a second array (O(N)). Iterate through first array and move all 1's in the order they appear to the second array. Iterate again and move the 0's that are left in the same order to the second array. All operations O(N). This is NOT in situ (in place) solution. A non-stable in situ solution is obtained by running the Quicksort partitioning algorithm once.

After conducting some research, it seems that the known O(N) solutions without any extra memory are not stable. There is academic research on efficient 0-1 stable sorting in situ (in place), but the solutions require some extra memory. I wonder if the original problem statement was not reproduced in an exact fashion. Without stability requirement the problem is very easy; it is also easy without in situ requirement. With BOTH of the requirements (in situ, stable) the solution seems to be elusive.

Among the answers here there is an algorithm that works in O(N) and is in situ, but only if the key field is (1) mutable and (2) can contain an integer instead of a single bit. This works but is not in situ 0-1 stable sorting, because it is assumed that there is O(log N) writable memory available per array element.