Introduction to Linear Sorting Algorithms

You are given a million exam scores and asked to sort them. Every score is a whole number from 0 to 100.

[5, 2, 5, 1, 2, 5]     scores range from 0 to 5 here

The usual answer is a comparison sort at O(N log N). That bound is not a limitation of any particular algorithm. Any sort that only ever compares two elements needs at least O(N log N) comparisons, and that has been proven.

But look at the input. A million values drawn from 101 possibilities means the same score appears about ten thousand times. Comparing two equal scores learns nothing.

Use the value itself instead