# Does there exist $O(n)$ worst case sorting algorithm for sorting a list of integers?

When I looked on wikipedia, all the sorting algorithms listed have worst case $O(n^2)$.

My question is suppose we are given a list of integers, each of which is in some fixed, finite set (i.e. $\{-1, 0, 1\}$). Does there exist a sorting algorithm that sorts this list in $O(n)$ time?

• I think your Wikipedia link shows $O(n \log n)$ worst case time complexity for Mergesort. Also, have a look here on Wikipedia. – Juho Dec 12 '14 at 21:33
• What research have you done? Have you looked in standard textbooks, such as CLRS? As I recall, many standard algorithms textbooks (including CLRS) answer your question. We expect you to make a significant effort and do significant self-study before asking here. – D.W. Dec 13 '14 at 6:03
• No, so far there isn't such. It is only a conjecture. The best one in all cases (even WC) is O(nsqrt(log log n)) which is almost O(n) but still. – user8 Nov 24 '15 at 13:37

There are some algorithms that could run in $O(n)$, but only for some specific inputs.

In general, if a sorting algorithm is based on comparisons then it will always take at least $\Omega(nlog(n))$ steps. The proof is pretty simple and based on an observation of a tree that contains $n!$ leaves, each one containing some order of $n$ elements to be sorted. You can read more about it here.

There are some sorting algorithms quaranteed to run in $O(nlog(n))$ (merge-sort or heapsort, for example), as well as some that have the worst case $O(n^2)$ (like quicksort). Note that merge-sort also uses $O(n)$ memory and Quicksort uses some memory through recursive calls. Heapsort sorts in place.

However, if your set fulfills some restrictions, then you may have an algorithm that can sort in $O(n)$. If you have to sort a big list of values that come only from quite a small range (by which I mean that the amount of values to sort is much greater than the number of possible values), you can use counting-sort. It will run in $O(n+k)$, where n is the size of your array (or list or whatever else) to sort and k is the number of possible values. For example: let's say you want to sort an array of $n = 10^6$ 8-bit chars. Counting sort would be ideal, as the size of your set of possible values is $k = 2^8 = 256$, and this is much less than 10 million. You can see that your $k$ does not add much to complexity compared to $n$, so you may say that counting sort will sort this in $O(n)$.

Other examples you should look at: radix-sort and bucket-sort are some other algorithms that could sort in $O(n)$ (average case).

There is no known algorithm that is $O(n)$ in the worst case. However if the numbers are bounded by some constant, i.e. the difference of the largest and the smallest element is less than some constant value, then radix sort works in time $O(n)$.

• The question has now been clarified. Since it is about lists where the smallest and largest element differ by at most some constant, there are linear-time algorithms. – David Richerby Dec 13 '14 at 0:38

I believe this paper gives the closest things to a known sorting algorithm for sorting that list in $O(n)$ time.

That paper's abstract is

Sorting n integers in the word-RAM model is a fundamental problem and a long-standing open problem is whether integer sorting is possible in linear time when the word size is $\omega(\log n)$.
In this paper we give an algorithm for sorting integers in expected linear time when the word size
is $\Omega(\log^2 n \log \log n)$. Previously expected linear time sorting was only possible for word size $\Omega(\log^{2+\epsilon} n)$. Part of our construction is a new packed sorting algorithm that sorts n integers of
w/b-bits packed in O(n/b) words, where b is the number of integers packed in a word of size w bits.
The packed sorting algorithm runs in expected $O\hspace{-0.04 in}\left(\hspace{-0.02 in}\frac{n}{b}\hspace{-0.03 in}\cdot \hspace{-0.03 in}(\log n + \log^2 b)\right)$ time.

.

Alternative Links to the Same Paper: 1,2,3

• The question has now been clarified. Since the range of the list is constant, counting sort is a genuine linear-time algorithm. – David Richerby Dec 13 '14 at 0:39