0

I have n integers in the interval [0,n^c] where c is some positive integer.

Which algorithm can I use to sort those integers in linear time?

I did look at RadixSort by my problem is the following: Given the interval the longest digit has at most cnlogn digits, so wouldnt RadixSort run in O(nlogn) time ?

CheckersGuy
  • 117
  • 10
  • I believe what you're looking for is a *radix sort*. – Chris Martin Jun 10 '17 at 12:04
  • 1
    Possible duplicate of [Sorting in linear time?](https://stackoverflow.com/questions/749585/sorting-in-linear-time) – trincot Jun 10 '17 at 12:04
  • @Coldspeed: I did have a look at radix Sort. But if I understand radix sort correctly I need m "Buckets" where m is the number of digits of the longest integer. Given my interval the "longest " digit has at most c*logn digits (base 10) – CheckersGuy Jun 10 '17 at 12:13
  • Wouldn`t the runtime of radixSort be O(nlogn) instead of O(n) since the digits have length c*nlogn ??? – CheckersGuy Jun 10 '17 at 12:21

1 Answers1

1

Use radix sort. You might say that it is not efficient enough, because the number of digits is log(n^c) so total time complexity is O(nlogn). However, you don't have to sort in base 10! you can probably convert your numbers to base n in constant time (depends on n), and radix sort in base n, since log_n(n^c) = c.

afifit
  • 106
  • 6
  • I think you are right. To convert one of those integers into base n I need at most c operations. So I can convert all of my n integers in c*n=O(n) (linear time). Additionally, the length of the digits is always bounded by c. – CheckersGuy Jun 10 '17 at 12:31