Sorting in linear time?

Question

Given an input set of n integers in the range [0..n^3-1], provide a linear time sorting algorithm.

This is a review for my test on thursday, and I have no idea how to approach this problem.

Solution 1

Also take a look at related sorts too: pigeonhole sort or counting sort, as well as radix sort as mentioned by Pukku.

Solution 2

Have a look at radix sort.

Solution 3

When people say "sorting algorithm" they often are referring to "comparison sorting algorithm", which is any algorithm that only depends on being able to ask "is this thing bigger or smaller than that". So if you are limited to asking this one question about the data then you will never get more than n*log(n) (this is the result of doing a log(n) search of the n factorial possible orderings of a data set).

If you can escape the constraints of "comparison sort" and ask a more sophisticated question about a piece of data, for instance "what is the base 10 radix of this data" then you can come up with any number of linear time sorting algorithms, they just take more memory.

This is a time space trade off. Comparason sort takes little or no ram and runs in N*log(n) time. radix sort (for example) runs in O(n) time AND O(log(radix)) memory.

Solution 4

It's really simple, if n=2 and numbers are unique:

• Construct an array of bits (2^31-1 bits => ~256MB). Initialize them to zero.
• Read the input, for each value you see set the respective bit in the array to 1.
• Scan the array, for each bit set, output the respective value.

Complexity => O(2n)

Otherwise, use Radix Sort:

Complexity => O(kn) (hopefully)

Solution 5

wikipedia shows quite many different sorting algorithms and their complexities. you might want to check them out

View more solutions