Radix sort run time

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.

Solution

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.