Sorting in O(n) time in a finite domain I've been stuck with this problem for 2 weeks. Any idea of how to aproach it?.


  Let $L$ be a list of $n$ different integer numbers, assume that the elements of $L$ are in the range $[1,750]$. Design a linear ordering algorithm to order the elements of $L$.


I already tried with insertion sort. But I'm not sure if my approach is right:


Construct an array of bits. Initialize them to zero.
Read the input, for each value you see set the respective bit in the array to 1.
Scan the array, for each bit set, output the respective value.


Complexity: $O(2n) = O(n)$

I also wanted to use radix sort but I can't understand how to apply it, any idea?
Bitvector approach is correct solution.

Problem statement tells that you are given $n$ different integers so there is no need to count multiple occurrence of number in sequence. This also allows you to cut down needed storage to $\lceil{\frac{750}{8}}\rceil = 94$ bytes.

Now the algorithm:

Input: $A$ - array of unique integers, 1 based

Output: None - we update given array

B[750] = 0; bitvector of len 750 initially set to 0
for each i in A
    B[i] = 1
k = 1
for j = 1 to 750
    if B[j]
        A[k] = j
        k = k+1


This obviously runs in $O(n)$ and uses $O(1)$ memory.

This can run in linear time because it isn't compare based sorting. As you correctly pointed out every compare based sorting must take at least $O(n \log n)$ steps.

This approach is special case of bucket sorting but we used information about problem statement (namely: unique integers and range of those integers)