[Solved]: Does there exist $O(n)$ worst case sorting algorithm for sorting a list of integers?

Problem Detail: 

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?

Asked By : Beached Whale

Answered By : 3yakuya

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35215

3.2K people like this

 Download Related Notes/Documents