Purchase Solution

sorting an array of integers in linear time

Not what you're looking for?

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 Summary

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

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

Free BrainMass Quizzes

Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.

Basic Computer Terms

We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.

Excel Introductory Quiz

This quiz tests your knowledge of basics of MS-Excel.

Word 2010: Tables

Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.

Basic UNIX commands

Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.