# 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

## 1 Answer

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