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?