title: No key-comparison sorting algorithm
body: <p>On this <a href="http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html" rel="nofollow">webpage</a> I can read:</p>
  
  <blockquote>
    <p>A few special case algorithms (one example is mentioned in
    Programming Pearls) can sort certain data sets faster than
    O(n*log(n)). These algorithms are not based on comparing the items
    being sorted and rely on tricks. It has been shown that no
    key-comparison algorithm can perform better than O(n*log(n)).</p>
  </blockquote>
  
  <p>It's the first time I hear about <strong>non-comparison algorithms</strong>. Could anybody give me an example of one of those algorithms and explain better how they solve the sorting problem faster then O(nlog(n))? What kind of tricks the author of that webpage is talking about?</p>
  
  <p>Any link to papers or other good source are welcome. Thank you.</p>