title: How to "sort" elements of 2 possible values in place in linear time?
body: <p>Suppose I have a function <code>f</code> and array of elements. </p>
  
  <p>The function returns <code>A</code> or <code>B</code> for any element; you could visualize the elements this way <code>ABBAABABAA</code>.</p>
  
  <p>I need to sort the elements according to the function, so the result is: <code>AAAAAABBBB</code></p>
  
  <p>The number of <code>A</code> values doesn't have to equal the number of <code>B</code> values. The total number of elements can be arbitrary (not fixed). Note that you don't sort chars, you sort objects that have a single char representation.</p>
  
  <p>Few more things:</p>
  
  <ul>
  <li>the sort should take linear time - <code>O(n)</code>,</li>
  <li>it should be performed in place,</li>
  <li>it should be a stable sort.</li>
  </ul>
  
  <p>Any ideas?</p>
  
  <hr>
  
  <p><strong>Note:</strong> if the above is not possible, do you have ideas for algorithms sacrificing one of the above requirements?</p>