Radix sort run time

Question

If we have some m>0 and need to provide an algorithm to sort n integers in the range 0 to n^m-1 in time O(mn). My suggestion is :

Radix-Sort(A,t)  // t is the digit length
for i=0 to t
    do Insertion-Sort A on digit i

My argument is that the above will run in O(mn) because for each digit t - Insertion sort will take O(n) time since the range for each run is small.

Is this the correct suggestion? What should be the space requirement of the above?

Thanks.

Answer 1

The space requirement is O(m + n) because you need the original numbers and m buckets to place the n items. The runtime is O(mn) which can be >> n which is the issue with radix sort. In all cases its O(mn) but the problem is that if m > n you get something larger than O(n^2). Depending on how it's written the memory can also be O(mn) in the worst case because you create m copies of the set of n numbers to sort on.

Answer 2

Its better to use Counting sort, when sorting discrete numbers of a small range, hence it guarantees the linearity of the search in respect to the size of data and the their range (insertion sort is a comparison sort with O(n^2) worst case complexity, but if the data were sorted in an oposite direction, the small range wont probably help you with insertion sort, because every element will be moved).

The space complexity when using counting sort will be O(n+k), where n is the size of the array and k is the range of the data. You can use the same array for sorting and returning the result, because you are sorting primitive data.