# When can one use a $O(n)$ time sorting algorithm?

Some sorting algorithms like counting sort/insertion sort can work in $O(n)$ time while other algorithms such as quicksort require $O(n \log n)$ time.

As I understand it, it's not always possible to use the $O(n)$ sorting algorithms. What are those cases when they can not be used?

-
are you looking at the complexity on already sorted input by any chance? –  jk. Feb 20 '13 at 14:10

In the comparison model, where all you are allowed to do is to compare two elements, and without further assumptions, we can prove that no sorting algorithm can do better than $O(n\log n)$.

If you want to sort in $O(n)$, you need either a stronger model, or additional assumptions.

For example, if you can bound the range of the numbers you are sorting, you can use bucket-sort, which is $O(n)$ (time).

A different example is spaghetti-sort: if you can implement the $\max$ function over $n$ elements in $O(1)$, then you can sort in $O(n)$.

You see here that different assumptions can allow you to sort in $O(n)$. There is no characterization of exactly which assumptions allow it.

-
Thanks, any idea what do i need to assume for radix/insertion/count sort? –  user6821 Feb 20 '13 at 12:47
Insertion sort requires no assumptions, and it's a terrible algorithm on large inputs - on average the runtime is $O(n^2)$. Counting sort requires that you have an a-priori bound on the maximal and minimal numbers that are in the array. Radix sort doesn't technically require any assumptions, but the runtime is $O(nk)$, where $k$ is the number of digits. So if you have numbers of size $\Omega(\log n)$, you are get $\Omega(n\log n)$ sorting, which is no better than quicksort. –  Shaull Feb 20 '13 at 12:57
Insertion sort requires $\Theta(n \log n)$ comparisons. It only requires $O(n)$ insertions, but each of these takes roughly $\log n$ comparisons. It's the data movement that kills you, and you could get around that by using fancy data structures (which would reduce it to $\Theta(n \log n)$ time, but the constant would not be competitive). –  Peter Shor Feb 20 '13 at 13:56
@PeterShor That's the reason that insertion sort can be a good choice for nearly sorted inputs. Real world implementations of quicksort do a partial sort, then call insertion sort to finish the job once the array is "mostly" sorted. –  Robert S. Barnes May 9 '13 at 5:46