How to sort a list with given range in O(n)
algorithm, sorting
Solution
You would usually need a non-comparison sort to sort in O(n) time, but this is if you are already given certain information. There are three "main" non-comparison sort algorithms to choose from: counting sort, radix sort, and bucket sort.
Use counting sort if you know that the input are small integers. By Wikipedia, "counting sort is only suitable to use in situations where the variation in keys is not significantly greater than the number of items." http://en.wikipedia.org/wiki/Counting_sort
You can use radix sort if all the numbers you are sorting have the same number of integers. Ex: 211, 311, 122.
Bucket sort may seem like the best option for you. Your approach sounds good, but you do not need an array from 1 to 2n with an index for each number. In bucket sort, you can have an array from 1 to 20, and have something like a linked list within each element. So if you were placing the number 109 it could correspond to the index 10.
Problem
If I have a list of size n and I know that the numbers in the list will be between 1 and 2n how would I go about solving it where the worst case would be O(n)? I was thinking that if it was between 1 and n I could just take the number and swap it with the value of the array at that number - 1 but then it wouldn't sort if there were any duplicate. I was thinking of a similar approach for the list having number between 1 and 2n but I can't seem to figure it out. Any help please?