Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
1  
are you looking at the complexity on already sorted input by any chance? –  jk. Feb 20 '13 at 14:10
add comment

1 Answer

up vote 7 down vote accepted

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.

share|improve this answer
    
Thanks, any idea what do i need to assume for radix/insertion/count sort? –  user6821 Feb 20 '13 at 12:47
2  
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
2  
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
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.