Sorting a large list of test scores You have a large list (say N > 10000) of test scores which you would like to sort. The test scores are between 1 and 100. What is quickest way to sort the list?

First thought. We have a O(N log N) bound, but we also have additional information about the quantities in the array, so I think we could do better.

Second thought: should we use hash tables, do we care about duplicates? Cant see how to use hash tables.

Third thought: does this have something to do with radix sorting? no idea.

Fourth thought: Could we sort this list by creating another list, and then pass through the original counting frequencies of elements occured. But would we need another pass to create a larger sorted list, which would be O(N^2). ie too large.

Is this a very easy question or a very hard question?
This is a very easy question, assuming all scores are integers. 

Here is the simplest algorithm in plain words. We will initiate count, an integer array of 100 zeros. For each score s, we will add 1 to count[s]. To produce the wanted sorted scores, we will output count[1] 1s, count[2] 2s, ..., and finally count[100] 100s. 

This kind of sorting algorithm is called counting sort.

The case of more than $N&gt;10000$ test scores that are between 1 and 100 is a prime usage of counting sort. The time complexity is $O(N)$ and the space complexity  is bounded by some small constant multiple of 100.

You may want to check counting sort for more information.