Is there a sorting algorithm available which has time complexity of O(N)?

Question

Most of the sorting algorithm have a complexity of O(NN) or O(NlogN) to achieve the result.However, there are algorithms which has a complexity of O(N) for specific set of input.I want to know if there is a sorting algorithm available that has a complexity of O(N) in all cases.

Answer 1

If you can only compare (check if two item are <,>,==) the values being sorted, then you can't do better than O(n log(n)). It's one of the few proven lower bounds on algorithms out there. The proof isn't too complex (check comparison sort on wikipedia for the details), but it's long enough not to repeat here.

If you can do things other than compare you have more flexibility. If you have numbers, you check out bucket sort (a type of radix sort), it makes O(n) sorting possible.

• BJ Myers: +1 for referring to bucket sort. The lower bound of O(n log n) only applies to comparison-based sorting algorithms.

Answer 2

No. The fastest general-purpose sorting algorithms are all O(nlgn). Actually Θ(nlgn), since it has been mathematically proven that comparison-based sorting algorithms cannot be any more efficient.

Here's a paper I found on comparison-based sorting algorithms that explains it. http://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf

Answer 3

Short answer is no.

O(N) algorithm is possible if each element of the input array belongs to a finite set. Say, if the input is always within the finite set [0..9]. Then you can create an array of size 10 , scan through the array and increment the corresponding index.

So, O(N) sorting algorithm in all cases will only be possible only if memory is infinite.

• smac89: If memory is infinite, what does that make the time? Not O(N)