What is the fastest way to sort 1 million integers when integers are from the range [1,100]?

Question

Notes: I've thought about Radix sort, bucket sort, counting sort.

Is there anyway to achieve big O(n)?

Answer 1

A counting sort would be the obvious choice under these circumstances. Yes, properly implemented it should have linear complexity.

Answer 2

With counting sort you get O(N) if the range is fixed and small (like 1..100 :))

Answer 3

You can use counting sort.

Counting sort (sometimes referred to as ultra sort or math sort) is a sorting algorithm which (like bucket sort) takes advantage of knowing the range of the numbers in the array to be sorted (array A).

Counting sort is a stable sort and has a running time of Θ(n+k), where n and k are the lengths of the arrays A (the input array) and C (the counting array), respectively. In order for this algorithm to be efficient, k must not be much larger than n.

In this case k is 100 and n is 1000000.

Answer 4

how about just counting the occurrence of each integer and then printing them all. sounds like O(n)

Answer 5

I assume, you mean you want to achieve a small O(n); then bucket sort would be fastest. In fact, since you know the range of the integers, then using bucket sort simply becomes a problem of counting the occurrences of the numbers which can be done in O(n), i.e. linear time.

The so-called counting sort is simply a special case of bucket sort.