The best we know for general case sorting is $O(n\log n)$ (which is also $\theta(n\log n)$ is decision tree model) and the problem of $O(n)$ sorting is open for turing machine models.

Under what models do we know $O(n)$ algorithms and how far they are deemed away from general models?

  • $\begingroup$ Sorting what? Integers? $\endgroup$ – Joshua Grochow May 24 at 19:07
  • $\begingroup$ Distinct non-negative integers is good enough scenario. $\endgroup$ – Turbo May 24 at 19:30

One obvious answer is "spaghetti sort", or in other words - sorting in a spaghetti model.

Intuitively, the spaghetti model says that your integers are given as lengths of (uncooked) spaghetti, and you sort them by placing them on a table, and then lowering your hand until you hit the tallest spaghetto (for spaghetto is the singular of spaghetti). You take that one out, and repeat.

A bit more formally, this model gives you the operation $\arg\max\{a_1,\ldots, a_n\}$ in $O(1)$.

Determining how "far" this is from a general model is a vague question. There is a trivial lower bound of $\Omega(n)$ on computing the maximum of $n$ elements in a RAM model (and an even worse bound of $\Omega(n\log n)$ in a single-tape Turing Machine), so this is not a realistic model. You could say that it's equivalent to a RAM model with oracle access to $\max$. I'm not sure how interesting that is.

Another cute aspect of this model is to consider it's physical properties, in the intuitive spaghetti description: recall that in this description, you lower your hand onto the spaghetti. Now, if you actually want to do this to an arbitrary number of spaghetti, then you would need an increasingly large hand. So this model induces a notion of "hand size" complexity.

  • $\begingroup$ As far as I can see, you need arg max rather than max to make it work. $\endgroup$ – Emil Jeřábek May 27 at 5:47
  • $\begingroup$ @EmilJeřábek - if you just want a sorted array whose numbers are those in the original array, then max is enough. However, I agree that if there is data associated with these numbers, then you indeed need argmax. I'll update the answer. $\endgroup$ – Shaull May 27 at 6:18
  • $\begingroup$ I think you need argmax even if you just sort integers, or even just a bunch of 0s and 1s. If you have just max, how do you compute the second largest element in $O(1)$ time? $\endgroup$ – Emil Jeřábek May 27 at 6:46
  • $\begingroup$ Yes, you're right. Of course. Thanks! $\endgroup$ – Shaull May 27 at 7:51

One thing to note is that there are a lot of practical situations where we can get better than $O(n \log n)$ sorting. I'm not sure where the best reference is, but this library has a link to a video talk by Fritz Henglein, who is who I've heard originated the technique (unfortunately the links to his actual papers are broken).

The idea is to extend radix sort (or a similar sort, like flag sort) to much wider categories of values. In radix sort, we know in advance that we only need to do a fixed number of passes to sort the data, because our integers have a fixed size. This leads to $O(m \times n)$ performance, where $m$ is the necessary number of passes. For fixed sized integers, $m$ is a constant, so this is effectively $O(n)$.

It turns out that you can apply this methodology to pretty much any 'algebraic' type. For instance, if we have a type $A$ sortable in $i$ passes and $B$ in $j$ passes, then $A \times B$ can be sorted using $i + j$ passes, where the specifics will depend on which sort of radix sort you're using ($A$ first for top-down, $B$ first for bottom-up). And if we consider a type like:

data Either a b = L a | R b

then the most obvious way to handle this is via the top-down flag sort style, where we first distinguish based on L or R and then proceed with $A$ and $B$, using $1 + \max(i,j)$ passes in general. So, any algebraic type with a finite maximum 'length' in this sense can be sorted in linear time (although the number of passes required may be large).

For recursive types (like strings), there is no fixed number of passes that are necessary, and in general it may require $\log n$ passes to fully distinguish $n$ values. (I'm not sure what a worst case example is. Probably something like sorting all prefixes of a given string.) However, particular examples might still run in sub-$(n \log n)$ time if they can be completely distinguished in fewer passes, and your algorithm is able to short-circuit the right way.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.