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?
How to sort a list containing bounded set of values in linear time when length is unknown?
sorting;big o
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.