sorting an array of integers in linear time

Not what you're looking for? Search our solutions OR ask your own Custom question.

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

How can I sort an array of integers in O(n) time, where different integers may have different numbers of digits, but the total number of digits over ALL the integers in the array is n?

My assumption is that radix sort is somehow involved.

Solution Preview

The result is also in the attached file, which is of the same content as the follows:

Let us use the following example to facilitate the explanation:

329
457
1086
8791
1978
2006
12469
12
518
9
178902
985730
234567
985
8943

In this example, the number of digits is 56, i.e., n = 56
Let m be the number of numbers, i.e., m = 15 in this example, then m < n

Let n1, n2, ... nk are the possible number of digits of each number in the array, so in this example,
n1 = 1, n2=2, n3 = 3, n4 = 4, n5 = 5, n6 = 6, ...

Solution Summary

This job targets sorting an array of integers in linear time.

$2.49