CODEWITHSUNDEEP
algorithmsorting
Mushahid Hussain
Mushahid Hussain

Reputation: 4055

Sorting algorithm that runs in time O(n) and also sorts in place

Is there any sorting algorithm which has running time of O(n) and also sorts in place?

Upvotes: 2

Views: 4198

Answers (5)

Antti Huima
Antti Huima

Reputation: 25522

No.

There's proven lower bound O(n log n) for general sorting.

Radix sort is based on knowing the numeric range of the data, but the in-place radix sorts mentioned here in practice require multiple passes for real-world data.

Upvotes: 4

Caleb
Caleb

Reputation: 125007

Spaghetti sort is O(n), though arguably not in-place. Also, it's analog only.

Upvotes: 0

Cᴏʀʏ
Cᴏʀʏ

Reputation: 107536

There are a few where the best case scenario is O(n), but it's probably because the collection of items is already sorted. You're looking at O(n log n) on average for some of the better ones.

With that said, the Wiki on sorting algorithms is quite good. There's a table that compares popular algorithms, stating their complexity, memory requirements (indicating whether the algorithm might be "in place"), and whether they leave equal value elements in their original order ("stability").

Here's a little more interesting look at performance, provided by this table (from the above Wiki):

Some will obviously be easier to implement than others, but I'm guessing that the ones worth implementing have already been done so in a library for your choosing.

Upvotes: 6

corsiKa
corsiKa

Reputation: 82579

Radix Sort can do that:

http://en.wikipedia.org/wiki/Radix_sort#In-place_MSD_radix_sort_implementations

Upvotes: 2

Rumple Stiltskin
Rumple Stiltskin

Reputation: 10405

Depends on the input and the problem. For example, 1...n numbers can be sorted in O(n) in place.

Upvotes: 0

Related Questions