title: Arrange 0's & 1's in a array
body: <p>This is one of an interview question which I had recently. I would like to know others perception of approach for this problem.</p>
  
  <p><strong>Question:</strong></p>
  
  <p>You are given a structure which holds employee details with two elements, <code>int</code> department and <code>string</code> name.</p>
  
  <pre><code>struct Employee
  { 
      string Name;
      int Dept;
  }
  </code></pre>
  
  <p>You are given details of N Employees, among which N/2 employees have <code>Dept == 0</code> and N/2 employees have <code>Dept == 1</code>, arranged in some arbitrary order. You need to sort the employee details based on their <code>Dept</code> value and it should be <a href="http://en.wikipedia.org/wiki/Stable_sort#Stability" rel="noreferrer">stable</a> i.e., the order of 1s and 0s in the original record should be maintained.</p>
  
  <p>For example, given the following sample data:</p>
  
  <pre>
  Name         Dept
  
  X1           0
  X2           1
  X3           0
  X4           1
  X5           0
  </pre>
  
  <p>after sorting the result should be:</p>
  
  <pre>
  Name         Dept
  
  X2           1
  X4           1
  X1           0
  X3           0
  X5           0
  </pre>
  
  <p>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).</p>