# sorting an array of integers in linear time

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.

Â© BrainMass Inc. brainmass.com December 15, 2022, 5:15 pm ad1c9bdddfhttps://brainmass.com/computer-science/arrays/70840

#### 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.