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 an employee details with two elements as int Deptartment and string Name.

struct Employee
{ 
    string Name;
    int Dept;
}

You are given details of N Employees among which there are N/2 employees Dept are 0's and N/2 employees dept are 1's arranged in some random 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 complexity should be o(N), with constant space for additional variables (which means sorting should be done in-place).