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

Question

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?

• jk.: are you looking at the complexity on already sorted input by any chance?

Answer 1

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.

• user6821: Thanks, any idea what do i need to assume for radix/insertion/count sort?
• Shaull: 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.
• Peter Shor: 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).
• Robert S. Barnes: @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.