title: Calculating the 90th percentile in O(n) time
body: <blockquote>
    <p><strong>Possible Duplicate:</strong><br>
    <a href="https://stackoverflow.com/questions/6121868/can-you-sort-n-integers-in-on-amortized-complexity">Can you sort n integers in O(n) amortized complexity?</a>  </p>
  </blockquote>
  
  
  
  <p>I have to write an algorithm which, given an unsorted list of integers, returns "the lowest number in the file which exceeds at least 90% of the numbers in the file", or -1 if no such number exists. Simple enough: I sort the list using merge sort, then start at the index 90% of the way along and look for the first number to be larger than the number before it.</p>
  
  <p>Part 2 of the question has got me stumped though. We're given some more information: the integers represent salaries, meaning they're all positive, and the vast majority of them are underneath 1,000,000. Apparently with this extra information it's possible to write an algorithm that solves the original problem in O(n) time, but I haven't the slightest clue how this is possible. Any ideas?</p>
  
  <p>I would post what I've done so far, but I haven't been able to come up with anything whatsoever.</p>