Looking for an O(n) algorithm

[ben_atkinson]

Hi
I'm trying to find an algorithm thats space complexity and run-time complexity are both O(n). The algorithm should sort an array of integers into order. I've had a look online but haven't been able to find anything and was wondering if you guys had any ideas on what I could use?

Thanks very much for your help

Ben

[Krishnaa]

I don't think such an algo exists.

[MrViggy]

Isn't an insertion sort O(n)?

Viggy

[MrViggy]

Hmm, maybe not:

http://en.wikipedia.org/wiki/Insertion_sort

My bad! ;-)

Viggy

[Zachm]

If you have any initial knowledge as to the range of the integers, you can use bucket sort:

http://en.wikipedia.org/wiki/Bucket_sort


It may only be applied assuming knowledge of range from which the integers are taken. Bucket sort works has complexity of O(n) where n is the size of the range.

There is no sorting algorithm (that makes no assumptions) that has run-time complexity lower than Ω(n log n).
This is proovable.

[MrViggy]

That's what I was thinking of, the bucket sort! D'OH! :D

Viggy