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.

Answer 1

Have a look at radix sort.

Answer 2

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

Answer 3

A Set of a limited range of numbers can be represented by a bitmap of RANGE bits. In this case, a 500mb bitmap, so for anything but huge lists, you'd be better off with Radix Sort. As you encounter the a number k, bitmap[k] = 1. Single traversal through list, O(N).

Answer 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)

Answer 5

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

Answer 6

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.

Answer 7

alike algo is possible:
M;// unsorted array
lngth; //number items of M
for(int i=0; i < lngth; i++)sorted[M[i]];
it's alone possible algo for linear complexity, but it has complexity O(k*N) by ram (N - number array elements, k -- element's len)