# 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;` 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