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

<p>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.</p>

<p>A bit more formally, this model gives you the operation <span class="math-container">$\arg\max\{a_1,\ldots, a_n\}$</span> in <span class="math-container">$O(1)$</span>.</p>

<p>Determining how "far" this is from a general model is a vague question. There is a trivial lower bound of <span class="math-container">$\Omega(n)$</span> on computing the maximum of <span class="math-container">$n$</span> elements in a RAM model (and an even worse bound of <span class="math-container">$\Omega(n\log n)$</span> 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 <span class="math-container">$\max$</span>. I'm not sure how interesting that is.</p>

<p>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. </p>

CC BY-SA 4.0
2019-05-27T05:47:17.680Z
As far as I can see, you need arg max rather than max to make it work.
Emil Jeřábek
CC BY-SA 4.0
2019-05-27T06:18:52.667Z
@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.
Shaull
CC BY-SA 4.0
2019-05-27T06:46:37.323Z
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?
Emil Jeřábek
CC BY-SA 4.0
2019-05-27T07:51:47.977Z
Yes, you're right. Of course. Thanks!
Shaull
CC BY-SA 4.0
2019-05-26T16:33:08.600Z
2019-05-27T07:52:33.270Z
2019-05-27T07:52:33.270Z
Shaull
<p>One thing to note is that there are a lot of practical situations where we can get better than <span class="math-container">$O(n \log n)$</span> sorting. I'm not sure where the best reference is, but <a href="https://hackage.haskell.org/package/discrimination" rel="nofollow noreferrer">this library</a> 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).</p>

<p>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 <span class="math-container">$O(m \times n)$</span> performance, where <span class="math-container">$m$</span> is the necessary number of passes. For fixed sized integers, <span class="math-container">$m$</span> is a constant, so this is effectively <span class="math-container">$O(n)$</span>.</p>

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

<pre><code>data Either a b = L a | R b
</code></pre>

<p>then the most obvious way to handle this is via the top-down flag sort style, where we first distinguish based on <code>L</code> or <code>R</code> and then proceed with <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, using <span class="math-container">$1 + \max(i,j)$</span> 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).</p>

<p>For recursive types (like strings), there is no fixed number of passes that are necessary, and <em>in general</em> it may require <span class="math-container">$\log n$</span> passes to fully distinguish <span class="math-container">$n$</span> 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-<span class="math-container">$(n \log n)$</span> time if they can be completely distinguished in fewer passes, and your algorithm is able to short-circuit the right way.</p>

CC BY-SA 4.0
2019-05-27T14:54:53.160Z
2019-05-27T14:54:53.160Z
Dan Doel
<p>The best we know for general case sorting is <span class="math-container">$O(n\log n)$</span> (which is also <span class="math-container">$\theta(n\log n)$</span> is decision tree model) and the problem of <span class="math-container">$O(n)$</span> sorting is open for turing machine models.</p>

<p>Under what models do we know <span class="math-container">$O(n)$</span> algorithms and how far they are deemed away from general models?</p>

CC BY-SA 4.0
2019-05-24T19:07:48.123Z
Sorting what? Integers?
Joshua Grochow
CC BY-SA 4.0
2019-05-24T19:30:55.700Z
Distinct non-negative integers is good enough scenario.
Turbo
<cc.complexity-theory><sorting>
Under what models do we know linear time sorting?
Turbo
# Under what models do we know linear time sorting?

(Asked by: username_0 on 2019-05-24)

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?

**Tags:** cc.complexity-theory, sorting
> **Comments:**
> **username_1**: Sorting what? Integers?  
> **username_0**: Distinct non-negative integers is good enough scenario.  

---

## 2 answers

### Answer by username_2 on 2019-05-26. Score: 5

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.

> **Comments:**
> **username_3**: As far as I can see, you need arg max rather than max to make it work.  
> **username_2**: @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.  
> **username_3**: 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?  
> **username_2**: Yes, you're right. Of course. Thanks!  

---

### Answer by username_4 on 2019-05-27. Score: 1

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.


---

