title: Is there an O(n) integer sorting algorithm?
body: <p>The last week I stumbled over <a href="http://www.pw.ethz.ch/people/research_group/mauej/personal/publications/MaueSanders2007.pdf" rel="noreferrer">this paper</a> where the authors mention on the second page:</p>
  
  <blockquote>
    <p>Note that this yields a linear running time for integer edge weights.</p>
  </blockquote>
  
  <p>The same on the third page:</p>
  
  <blockquote>
    <p>This yields a linear running time for integer edge weights and O(m log n) for comparison-based sorting.</p>
  </blockquote>
  
  <p>And on the 8th page:</p>
  
  <blockquote>
    <p>In particular, using fast integer sorting would probably accelerate GPA considerably. </p>
  </blockquote>
  
  <p>Does this mean that there is a O(n) sorting algorithm under special circumstances for integer values? Or is this a specialty of graph theory?</p>
  
  <p><strong>PS:</strong><br>
  It could be that reference [3] could be helpful because on the first page they say:</p>
  
  <blockquote>
    <p>Further improvements have been achieved for [..] graph classes such as integer edge weights [3], [...]</p>
  </blockquote>
  
  <p>but I didn't have access to any of the scientific journals.</p>