Given a list of integers whose length is unknown, and each of its elements lies between 1 to 1000, how does one sort this list in linear time?
You know that every element of your
int arr; is in
So have an array of counters,
int cnt; in C parlance. Clear it (all zeros).
Then, read the
arr array sequentially. Suppose that you have read the value
x at index
x==arr[i]). Then increment its counter, so
When you have reached the end of the input array
arr, iterate on
for (int i=0; i<=1000; i++) and output the number
This is O(n) (because the bound 1000 is a constant).
This sort is often known as the counting sort.