2

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

Jared Farrish
  • 48,585
  • 17
  • 95
  • 104
Mushahid Hussain
  • 4,052
  • 11
  • 43
  • 62

5 Answers5

6

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.

Cᴏʀʏ
  • 105,112
  • 20
  • 162
  • 194
  • nitpick: that a sorting algorithm is in-place is completely orthogonal to it being stable. – abeln Apr 17 '11 at 02:38
  • @abeln: You're correct. For some reason I was thinking of leaving equal elements "in order" or "in place" and not of temporary storage needed during sorting. I've updated my answer. – Cᴏʀʏ Apr 17 '11 at 05:49
4

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.

Antti Huima
  • 25,136
  • 3
  • 52
  • 71
2

Radix Sort can do that:

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

corsiKa
  • 81,495
  • 25
  • 153
  • 204
  • 1
    As long as the maximum number of digits is constant. – ThomasMcLeod Apr 16 '11 at 18:16
  • 1
    @ThomasMcLeod That's not necessarily true. First there's no requirement that we're sorting numbers. Second, if you're doing by the bits instead of digits they're always the same length. Third, even if you're not using bits, if you're using the string representation of the number, you can prepend 0s to the front to simulate them being the same length. – corsiKa Apr 16 '11 at 18:43
  • It is true. Even if you use bits or some string representation, you must pre-determine the bit length or string length. This is the only way to limit tree depth to achieve a O(1) runtime. Otherwise, _best case_ runtime is Ω(n log n). see http://en.wikipedia.org/wiki/Radix_sort#Efficiency. – ThomasMcLeod Apr 17 '11 at 00:39
  • 1
    Your interpretation of that article is hazy at best. Radix sort is `O(nk)`, worst case and best case. I don't know how you're arriving at O(1) runtime. Your comment "as long as the maximum number of digits is constant" implies that some inputs won't be valid for having a fluctuating maximum length. That's simply incorrect. You don't even need to make a pass through the input to determine the maximum number of digits. You simply look at the first one, then the second, then the third, etc... If you reach the fourth digit of a 2 length string, you pretend you found the lowest possible value. – corsiKa Apr 17 '11 at 04:00
  • I meant O(1) per element. By tree I was referring to the decision tree of each element. Radix sort is `O(kn) = O(n)` only if k is a constant independent of n. This is not alway true. – ThomasMcLeod Apr 17 '11 at 17:00
  • @Thomas I'm sorry but you're factually mistaken. There are no conditions under which radix sort is not `O(kn)`. You may be able to express k as a function of n, but that doesn't change the mechanics (or running time) of the sort - it merely provides more information about it. Furthermore, if you operate at the bit level instead of the string level, k is constant (31 for ints and 63 for longs). – corsiKa Apr 17 '11 at 19:03
  • I didn't say that it wasn't O(kn). The question is about a sort that runs in O(n). To get O(n), you must get the k to drop out. To get the k to drop out, k must be a constant independent of n. This is a requirement of the definition of Big-O. Now, if you say that you're selecting the algorithm to run on a particular dataset on a particular architecture that has certain limits like 32 bits or whatever, then you can fix k at some constant value. But in the general case, as a pure algorithm, k is in Ω(log n). Hence the general case for radix sort is Ω(n log n). – ThomasMcLeod Apr 17 '11 at 23:48
  • @Thomas: This is kind of a tricky area, especially when OP does not specify the model of computation. If you just take a plain old Turing Machine with random access, then radix sort is _linear_ time, as the size of input is nlogn (or O(n K) to be precise). It is Omega(nlogn), but the size of input itself is Omega(nlogn), and O(n) is obviously insufficient (but trivial to discuss). If you take a RAM model, then k is independent of n, and so O(kn) = O(n). It must be some magical machine where you allow as input n arbitrary length integers and call the size of input as Theta(n)... –  Apr 18 '11 at 22:41
  • @Moron, I've been thinking about your comment. It seems that the magic in the machine has less to do with the computation model and more to do with the bounds on the data and whether you can compare arbitrary length data in `O(1)` time. If comparison is `O(1)`, then we have `Ω(n log n)`. If not, then we have `Ω(n log^2 n)`, the extra log coming from the comparison at each node. On the other hand, if we limit data size, then both logs drop out and we have `Θ(n)`. All of this assumes `Θ(1)` access to memory. If we assume sequential access, as in a TM, then `Ω(n^2 log^3 n)` seems correct. – ThomasMcLeod Apr 21 '11 at 18:39
  • @Thomas: In the Word RAM model comparisons are assumed to be O(1), so the model does matter. If you think about it, even finding maximum of n numbers is technically not O(n) in the models you speak of. But if we consider the word RAM model (which is the closest model to real computers) then we do have O(n) time algorithms. In fact most algorithm analyses assume Word RAM model. This link might be useful: http://cstheory.stackexchange.com/questions/2656/which-model-of-computation-is-the-best –  Apr 21 '11 at 19:16
0

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

Rumple Stiltskin
  • 9,597
  • 1
  • 20
  • 25
0

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

Caleb
  • 124,013
  • 19
  • 183
  • 272