2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ are you looking at the complexity on already sorted input by any chance? $\endgroup$
    – jk.
    Feb 20, 2013 at 14:10

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, any idea what do i need to assume for radix/insertion/count sort? $\endgroup$
    – user6821
    Feb 20, 2013 at 12:47
  • 2
    $\begingroup$ 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. $\endgroup$
    – Shaull
    Feb 20, 2013 at 12:57
  • 2
    $\begingroup$ 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). $\endgroup$
    – Peter Shor
    Feb 20, 2013 at 13:56
  • 1
    $\begingroup$ @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. $\endgroup$
    – Robert S. Barnes
    May 9, 2013 at 5:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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