Sorting an array with elements ranging from 0 to 9999

Question

I recently stumbled upon a C++ problem. Here goes.

Suppose you know that all the values in an integer array fall into the range 0 to 9999. Show that it is possible to write a O(N) algorithm to sort arrays with this restriction

To my understanding an algorithm of O(N) is one where you go through a certain set of O(1) operations N times. Now for the life of me I can't comprehend how you would go about writing a program that sorts an array of numbers with respect to O(N). Sorting in its most basic form consists of comparing numbers with each other and there is no algorithm for doing that in one iteration and ending up with a sorted array.

In the question it makes the point that an element of this array can only have the value within the range of 0-9999. I can understand from the question that this restriction is what makes the whole thing possible and I should use it in my Algorithm in order to reach a solution. But I'm still getting nowhere. All the sorting Algorithms that I know of (Selection, Insertion, Merge, Quick ...) all have running times larger than O(N) with the minimum being O(log N).

I can understand that some of these algorithms can have running times of O(N), but only on their best cases. But I don't think the question is being asked in that respect.

If anyone can shed any insight on this problem I would appreciate it.

Answer 1

Radix sort. O(4n) is O(n).

Answer 2

Counting sort (see http://en.wikipedia.org/wiki/Counting_sort). Only comparison sorts are Omega(n lg n).