Author |
Topic: Sort (Read 335 times) |
|
mad
Junior Member
Posts: 118
|
Show how to sort n integers in the range 0 to n^2-1 in O(n) time. I think convert the number into base2 and apply radix sort. Is this correct?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sort
« Reply #1 on: Mar 8th, 2008, 2:25am » |
Quote Modify
|
What sort of computer do you have that doesn't already store numbers in binary? I'm not sure whether the preferred answer is radix sort, but it works.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
m_aakash
Junior Member
Posts: 96
|
|
Re: Sort
« Reply #2 on: Mar 8th, 2008, 1:39pm » |
Quote Modify
|
if you use radix sort with radix 2 then it will take O(n log(n^2-1)) time in worst case. this is no longer a linear solution.
|
« Last Edit: Mar 8th, 2008, 1:40pm by m_aakash » |
IP Logged |
|
|
|
|