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 als开发者_高级运维o sorts in place?

---

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").

• http://en.wikipedia.org/wiki/Sorting_algorithm

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

• http://en.wikipedia.org/wiki/File:SortingAlgoComp.png

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.

---

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.

---

Radix Sort can do that:

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

---

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

---

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