Sort n numbers between range [0,2n] in linear time

Question

Suppose list L contains n numbers that are known to be in the range [0, 2 n]. Design an algorithm for sorting L in linear time.

I'm not too sure how to solve this. I believe radix sort is O(dn).

Answer 1

Looks like homework. What's about this algorithm in some pseudo code:

• Construct a flag array in size 2n
• Forall numbers x in list, store flag[x] = true
• For i=0 to 2n print i if flag[i] is true.

All iteration loops are bound by O(n).

Answer 2

Something like the following:

1. Define an array of size 2n initialised with 0 values.
2. For each item in L, increment arr[L_i].
3. Loop through the array returning all items with value > 0.

This algorithm can be easily modified to handle non-distinct values in L by modifying step 3 slightly.