title: Fast sort algorithms for arrays with mostly duplicated elements?
body: <p>What are efficient ways to sort arrays that have mostly a small set of duplicated elements?  That is, a list like:</p>
  
  <p>{ 10, 10, 55, 10, 999, 8851243, 10, 55, 55, 55, 10, 999, 8851243, 10 }</p>
  
  <p>Assuming that the order of <code>equal</code> elements doesn't matter, what are good worst-case/average-case algorithms?</p>