# How to sort a list containing bounded set of values in linear time when length is unknown?

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?

• sorry about that. I thought I would clarify all the constraints when describing the problem. Dec 3, 2015 at 15:04
• integer is inferred but suggest you add that to the question to be clear Dec 3, 2015 at 16:25

You know that every element of your int arr[]; is in [1;1000].

So have an array of counters, int cnt[1001]; in C parlance. Clear it (all zeros).

Then, read the arr[] array sequentially. Suppose that you have read the value x at index i (so x==arr[i]). Then increment its counter, so cnt[x]++;

When you have reached the end of the input array arr, iterate on cnt so for (int i=0; i<=1000; i++) and output the number i exactly cnt[i] times.

This is O(n) (because the bound 1000 is a constant).

This sort is often known as the counting sort.

• Woah! that was such a simple and nice solution. Thanks :) Dec 3, 2015 at 14:57
• Although this achieves linearity, is there a practical reason you would want to normalize the time to the highest possible value like this? Dec 3, 2015 at 14:57
• Don't know. Just got asked in interview, suggested radix sort but got stuck.. I rarely use counting , radix, shell etc linear time sorting...i kinda forgot them and paid for it :( Dec 3, 2015 at 15:06
• BTW, I did not know about counting sort terminology; I figured out that algorithm myself. Dec 3, 2015 at 18:19
• That must be why you explained it so much clearly and suscintly than wikipedia Dec 5, 2015 at 23:08