<p>As it turns out, my question is quite irrelevant after all. Indeed, I am working on the RAM machine with uniform cost measure (i.e., we have registers whose registers are not necessarily of constant size but can store integers of logarithmic size in the input at most, and operations on these registers take constant time, including at least addition). And in fact, in this model, sorting integers (by essentially performing a radix sort) can be done in linear time. This is explained in the 1996 paper by Grandjean, <em><a href="https://link.springer.com/article/10.1007%2FBF02127798" rel="nofollow noreferrer">Sorting, linear time and the satisfiability problem</a></em>.</p>

<p>(This does not answer my question of whether there are well-studied notions of "almost sorting" a set of integers, but for them to be interesting one would probably need these weaker notions to be easier to enforce, i.e., work on a weaker model or somehow run in sublinear time. However, I'm currently not aware of a sense in which this would be the case.)</p>

CC BY-SA 4.0
2019-06-13T15:58:12.570Z
2019-06-13T15:58:12.570Z
Antoine Amarilli 'a3nm'
<p>This sounds a lot like the ASort algorithm. See this article by Giesen et. al.:</p>

<p><a href="https://www.inf.ethz.ch/personal/smilos/asort3.pdf" rel="nofollow noreferrer">https://www.inf.ethz.ch/personal/smilos/asort3.pdf</a></p>

<p>Unfortunately, the running time is not quite linear. The article above proves that any comparison-based randomized algorithm ranking $n$ items within $n^2/\nu(n)$ has a lower bound of $n*log (\nu(n))$ (assuming $\nu(n) &lt; n$).</p>

<hr>

<p><strong>EDIT</strong>, in response to the clarifications in the question:</p>

<p>What you're doing is simply a <strong>bucket sort</strong>. However, the algorithm for bucket sort isn't linear in this case. The problem: you have to sum the natural numbers and then perform division on each one of them. Since the numbers are unbounded in size, $N/V[i]$ is no longer a constant-time operation. It will take longer to perform the more numbers you need to sum.</p>

<p>How much longer? Division depends on the number of digits, so it's $lg(n)$, times $n$ division operations. That probably sounds familiar. :)</p>

CC BY-SA 3.0
2017-04-25T15:44:28.927Z
Thanks for pointing us to this article! Indeed it is a bit related to the question. However, my algorithm (neither the original version nor the slightly different revised version) is not so similar to ASort;. First, I believe my algorithm runs in $O(n)$, not in superlinear time like ASort. Second, criterion (\*) is pretty different from approximating Spearman's footrule distance; e.g., criterion (\*) is more or less tight depending on the values of the integers, unlike the footrule distance. Third, althout both our algorithm and ASort are bucketing elements, the criteria are pretty different.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2017-04-27T16:21:12.443Z
@a3nm The clarification of what you posted above suggests you're using a **bucket sort**, which is linear (and not comparison-based, which means testing two items against each other). The problem is that it doesn't work for all mathematical integers. It only works if the integer size is bounded.
Trixie Wolf
CC BY-SA 3.0
2017-04-28T06:22:10.187Z
When you say "It only works if the integer size is bounded", I think this is only true if I were actually sorting the integers. But in general the algorithm I posted does not actually sort them, it only enforces the weaker criterion (\*). So I do think it runs in linear time even when the integer size is not bounded.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2017-04-29T02:04:05.483Z
@a3nm It isn't linear. See my expanded response above.
Trixie Wolf
CC BY-SA 3.0
2017-05-09T09:42:07.317Z
Thanks for the answer, and sorry about the delay. I think there is some confusion about the model. I am working in the RAM model with uniform time measure (as in van Emde Boas, Machine Models and Simulations, in Handbook of Computation): so the numbers that I manipulate can have logarithmic size, but arithmetic operations on these numbers have unit cost. I have edited my question accordingly. I think that, in this model, the algorithm that I propose really runs in linear time (but of course in this model the $n \log n$ lower bound for actual comparison-based sorting still applies).
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2017-04-24T19:10:39.117Z
2017-04-29T02:03:45.313Z
2017-04-29T02:03:45.313Z
Trixie Wolf
<p>I am interested in sorting an array of positive integer values <span class="math-container">$L = v_1, \ldots, v_n$</span> in linear time (in the RAM model with uniform cost measure, i.e., integers can have up to logarithmic size but arithmetic operations on them are assumed to take unit time). Of course, this is impossible with comparison-based sorting algorithms, so I am interested in computing an "approximate" sort, i.e., computing some permutation <span class="math-container">$v_{\sigma(1)}, \ldots, v_{\sigma(n)}$</span> of <span class="math-container">$L$</span> which is not really sorted in general but a "good approximation" of the sorted version of <span class="math-container">$L$</span>. I will assume that we are sorting the integers in decreasing order because it makes the sequel a bit more pleasant to state, but of course one could phrase the problem the other way round.</p>

<p>One possible criterion for an approximate sort is the following (*): letting <span class="math-container">$N$</span> be <span class="math-container">$\sum_i v_i$</span>, for every <span class="math-container">$1 \leq i \leq n$</span>, we require that <span class="math-container">$v_{\sigma(i)} \leq N/i$</span> (i.e., the "quasi-sorted" list is bounded from above by the decreasing function <span class="math-container">$i \mapsto N/i$</span>). It is easy to see that the actual sort satisfies this: <span class="math-container">$v_{\sigma(2)}$</span> must be no greater than <span class="math-container">$v_{\sigma(1)}$</span> so it is at most <span class="math-container">$(v_{\sigma(1)} + v_{\sigma(2)})/2$</span> which is <span class="math-container">$\leq N/2$</span>, and in general <span class="math-container">$v_{\sigma(i)}$</span> must be no greater than <span class="math-container">$(\sum_{j \leq i} v_{\sigma(i)})/i$</span> which is <span class="math-container">$\leq N/i$</span>.</p>

<p>For instance, requirement (*) can be achieved by the algorithm below (suggested by @Louis). My question is: <strong>Is there existing work on this task of "almost sorting" integers in linear time, by imposing some requirement like (*) that the real sort would satisfy? Does the algorithm below, or some variant of it, have an established name?</strong></p>

<p><em>Edit: fixed the algorithm and added more explanations</em></p>

<hr>

<p>Algorithm:</p>

<pre><code>INPUT: V an array of size n containing positive integers
OUTPUT: T

N = Σ_{i&lt;n} V[i]
Create n buckets indexed by 1..n
For i in 1..n
| Add V[i] into the bucket min(floor(N/V[i]),n)
+

For bucket 1 to bucket n
| For each element in the bucket
| | Append element to T
| +
+
</code></pre>

<p>This algorithm works as intended for the following reasons:</p>

<ol>
<li>If an element <span class="math-container">$v$</span> is in the bucket <span class="math-container">$j$</span> then <span class="math-container">$v ≤ N/j$</span>.

<blockquote>
  <p><span class="math-container">$v$</span> is put into the bucket <span class="math-container">$j=\min(N/v,n)$</span>, thus <span class="math-container">$j ≤ \lfloor N/v\rfloor ≤ N/v$</span></p>
</blockquote></li>
<li>If an element <span class="math-container">$v$</span> is in the bucket <span class="math-container">$j$</span> then either <span class="math-container">$N/(j+1) &lt; v$</span> or <span class="math-container">$j=n$</span>.

<blockquote>
  <p><span class="math-container">$v$</span> is put into the bucket <span class="math-container">$j=\min(N/v,n)$</span>, thus <span class="math-container">$j = \lfloor N/v \rfloor$</span> or <span class="math-container">$j=n$</span>. In the first case <span class="math-container">$j=\lfloor N/v\rfloor$</span> which means <span class="math-container">$j ≤ N/v &lt; j+1$</span> and thus <span class="math-container">$N/(j+1) &lt; v$</span>.</p>
</blockquote></li>
<li><p>For <span class="math-container">$j&lt;n$</span>, there are, at most, <span class="math-container">$j$</span> elements in the buckets from 1 to <span class="math-container">$j$</span>.</p>

<blockquote>
  <p>Let <span class="math-container">$j&lt;n$</span> and let <span class="math-container">$k$</span> be the total number of elements in one of the
  buckets 1..j. By <strong>2.</strong> we have that every element <span class="math-container">$v$</span> in a bucket <span class="math-container">$i$</span> (with <span class="math-container">$i ≤ j$</span>) is such that <span class="math-container">$N/(j+1)≤N/(i+1)&lt;v$</span>. Therefore the sum <span class="math-container">$K$</span> of all elements in the buckets from <span class="math-container">$1$</span> to <span class="math-container">$j$</span> is greater than <span class="math-container">$k×N/(J+1)$</span>. But this sum <span class="math-container">$K$</span> is also less than <span class="math-container">$N$</span> thus <span class="math-container">$k×N/(j+1) &lt; K ≤ N$</span> and thus  <span class="math-container">$k/(j+1) &lt; 1$</span> which gives us <span class="math-container">$k&lt;j+1$</span> or <span class="math-container">$k≤j$</span>.</p>
</blockquote></li>
<li><p><span class="math-container">$T$</span> satisfies (*) i.e. the <span class="math-container">$j$</span>-th element of <span class="math-container">$T$</span> is such that <span class="math-container">$T[j] ≤ N/j$</span></p>

<blockquote>
  <p>By <strong>3.</strong> we have that <span class="math-container">$T[j]$</span>, the <span class="math-container">$j$</span>-th element of <span class="math-container">$T$</span>, comes from a bucket <span class="math-container">$i$</span> with <span class="math-container">$i ≥ j$</span> therefore <span class="math-container">$T[j] ≤ N/i ≤ N/j$</span>.</p>
</blockquote></li>
<li><p>This algorithm takes linear time.</p>

<blockquote>
  <p>The computation of <span class="math-container">$N$</span> takes linear time. Buckets can be implemented with a linked-list which has <span class="math-container">$O(1)$</span> insertion and iteration. The nested loop runs as many times as there are elements (i.e. <span class="math-container">$n$</span> times).</p>
</blockquote></li>
</ol>

CC BY-SA 3.0
2017-04-24T21:28:25.403Z
Not to dismiss the question (+1, it's a good one) but wouldn't radix sort do more than what you need?
user541686
CC BY-SA 3.0
2017-04-25T15:43:26.977Z
@Mehrdad: Thanks for your comment! Radix sort would sort the integers, but it would take time $O(n \log (\max_i v_i))$.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2017-04-25T17:34:16.157Z
Could you comment on what exactly is undesirable about that time complexity? Do you have one *very* large integer and everything else is small, for example?
user541686
CC BY-SA 3.0
2017-04-25T19:33:11.587Z
@Mehrdad: We intend to use the quasi-sort routine in another algorithm, and we really want the time complexity to be linear, not $O(n \log n)$. This is needed to establish the theoretical result that we want.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2017-04-27T07:53:12.183Z
@a3nm radix sort is not O(n log n) it is O(n) hence linear if the size of integers is fixed, for example 32 bits numbers or 64 bits numbers. Does the numbers you sort have variable size?
Xavier Combelle
CC BY-SA 3.0
2017-04-27T08:39:22.577Z
@XavierCombelle: Yes, I'm working in the RAM model and I cannot suppose that the input integers are bounded by a constant.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-06-13T20:22:02.767Z
You might be interested in "[Approximate Data Structures with Applications](https://scholar.google.com/scholar?cluster=14139712545998684808&hl=en&as_sdt=0,22)", which describes heap-like data structures that allow a form of approximate sorting.  Namely, for a given $\epsilon>0$, ordering the elements such that, after adjusting each element by at most at $1+\epsilon$ factor, the adjusted elements would be in sorted order.  This can be done in linear time even as $\epsilon$ tends (slowly) to zero with the number of elements.
Neal Young
CC BY-SA 4.0
2019-06-15T17:16:42.087Z
@NealYoung: Thanks for the pointer! For our purposes we no longer need approximate sorting as we can do linear-time sorting in our model, but this reference looks relevant nevertheless.
Antoine Amarilli 'a3nm'
<reference-request><time-complexity><sorting>
"Almost sorting" integers in linear time
Antoine Amarilli 'a3nm'
# "Almost sorting" integers in linear time

(Asked by: username_0 on 2017-04-24)

I am interested in sorting an array of positive integer values $L = v_1, \ldots, v_n$ in linear time (in the RAM model with uniform cost measure, i.e., integers can have up to logarithmic size but arithmetic operations on them are assumed to take unit time). Of course, this is impossible with comparison-based sorting algorithms, so I am interested in computing an "approximate" sort, i.e., computing some permutation $v_{\sigma(1)}, \ldots, v_{\sigma(n)}$ of $L$ which is not really sorted in general but a "good approximation" of the sorted version of $L$. I will assume that we are sorting the integers in decreasing order because it makes the sequel a bit more pleasant to state, but of course one could phrase the problem the other way round.
One possible criterion for an approximate sort is the following (*): letting $N$ be $\sum_i v_i$, for every $1 \leq i \leq n$, we require that $v_{\sigma(i)} \leq N/i$ (i.e., the "quasi-sorted" list is bounded from above by the decreasing function $i \mapsto N/i$). It is easy to see that the actual sort satisfies this: $v_{\sigma(2)}$ must be no greater than $v_{\sigma(1)}$ so it is at most $(v_{\sigma(1)} + v_{\sigma(2)})/2$ which is $\leq N/2$, and in general $v_{\sigma(i)}$ must be no greater than $(\sum_{j \leq i} v_{\sigma(i)})/i$ which is $\leq N/i$.
For instance, requirement (*) can be achieved by the algorithm below (suggested by @Louis). My question is: Is there existing work on this task of "almost sorting" integers in linear time, by imposing some requirement like (*) that the real sort would satisfy? Does the algorithm below, or some variant of it, have an established name?
Edit: fixed the algorithm and added more explanations

Algorithm:
INPUT: V an array of size n containing positive integers
OUTPUT: T

N = Σ_{i
This algorithm works as intended for the following reasons:

If an element $v$ is in the bucket $j$ then $v ≤ N/j$.


$v$ is put into the bucket $j=\min(N/v,n)$, thus $j ≤ \lfloor N/v\rfloor ≤ N/v$

If an element $v$ is in the bucket $j$ then either $N/(j+1) < v$ or $j=n$.


$v$ is put into the bucket $j=\min(N/v,n)$, thus $j = \lfloor N/v \rfloor$ or $j=n$. In the first case $j=\lfloor N/v\rfloor$ which means $j ≤ N/v < j+1$ and thus $N/(j+1) < v$.

For $j, there are, at most, $j$ elements in the buckets from 1 to $j$.

Let $j and let $k$ be the total number of elements in one of the
  buckets 1..j. By 2. we have that every element $v$ in a bucket $i$ (with $i ≤ j$) is such that $N/(j+1)≤N/(i+1). Therefore the sum $K$ of all elements in the buckets from $1$ to $j$ is greater than $k×N/(J+1)$. But this sum $K$ is also less than $N$ thus $k×N/(j+1) < K ≤ N$ and thus  $k/(j+1) < 1$ which gives us $k or $k≤j$.

$T$ satisfies (*) i.e. the $j$-th element of $T$ is such that $T[j] ≤ N/j$

By 3. we have that $T[j]$, the $j$-th element of $T$, comes from a bucket $i$ with $i ≥ j$ therefore $T[j] ≤ N/i ≤ N/j$.

This algorithm takes linear time.

The computation of $N$ takes linear time. Buckets can be implemented with a linked-list which has $O(1)$ insertion and iteration. The nested loop runs as many times as there are elements (i.e. $n$ times).

**Tags:** reference-request, time-complexity, sorting
> **Comments:**
> **username_1**: Not to dismiss the question (+1, it's a good one) but wouldn't radix sort do more than what you need?  
> **username_0**: @Mehrdad: Thanks for your comment! Radix sort would sort the integers, but it would take time $O(n \log (\max_i v_i))$.  
> **username_1**: Could you comment on what exactly is undesirable about that time complexity? Do you have one *very* large integer and everything else is small, for example?  
> **username_0**: @Mehrdad: We intend to use the quasi-sort routine in another algorithm, and we really want the time complexity to be linear, not $O(n \log n)$. This is needed to establish the theoretical result that we want.  
> **username_2**: @a3nm radix sort is not O(n log n) it is O(n) hence linear if the size of integers is fixed, for example 32 bits numbers or 64 bits numbers. Does the numbers you sort have variable size?  
> **username_0**: @XavierCombelle: Yes, I'm working in the RAM model and I cannot suppose that the input integers are bounded by a constant.  
> **username_3**: You might be interested in "[Approximate Data Structures with Applications](https://scholar.google.com/scholar?cluster=14139712545998684808&hl=en&as_sdt=0,22)", which describes heap-like data structures that allow a form of approximate sorting.  Namely, for a given $\epsilon>0$, ordering the elements such that, after adjusting each element by at most at $1+\epsilon$ factor, the adjusted elements would be in sorted order.  This can be done in linear time even as $\epsilon$ tends (slowly) to zero with the number of elements.  
> **username_0**: @NealYoung: Thanks for the pointer! For our purposes we no longer need approximate sorting as we can do linear-time sorting in our model, but this reference looks relevant nevertheless.  

---

## 2 answers

### Answer by username_0 on 2019-06-13. Score: 3 | Accepted answer

As it turns out, my question is quite irrelevant after all. Indeed, I am working on the RAM machine with uniform cost measure (i.e., we have registers whose registers are not necessarily of constant size but can store integers of logarithmic size in the input at most, and operations on these registers take constant time, including at least addition). And in fact, in this model, sorting integers (by essentially performing a radix sort) can be done in linear time. This is explained in the 1996 paper by Grandjean, *[Sorting, linear time and the satisfiability problem](https://link.springer.com/article/10.1007%2FBF02127798)*.

(This does not answer my question of whether there are well-studied notions of "almost sorting" a set of integers, but for them to be interesting one would probably need these weaker notions to be easier to enforce, i.e., work on a weaker model or somehow run in sublinear time. However, I'm currently not aware of a sense in which this would be the case.)


---

### Answer by username_4 on 2017-04-24. Score: 8

This sounds a lot like the ASort algorithm. See this article by Giesen et. al.:

<https://www.inf.ethz.ch/personal/smilos/asort3.pdf>

Unfortunately, the running time is not quite linear. The article above proves that any comparison-based randomized algorithm ranking $n$ items within $n^2/\nu(n)$ has a lower bound of $n\*log (\nu(n))$ (assuming $\nu(n) < n$).

---

**EDIT**, in response to the clarifications in the question:

What you're doing is simply a **bucket sort**. However, the algorithm for bucket sort isn't linear in this case. The problem: you have to sum the natural numbers and then perform division on each one of them. Since the numbers are unbounded in size, $N/V[i]$ is no longer a constant-time operation. It will take longer to perform the more numbers you need to sum.

How much longer? Division depends on the number of digits, so it's $lg(n)$, times $n$ division operations. That probably sounds familiar. :)

> **Comments:**
> **username_0**: Thanks for pointing us to this article! Indeed it is a bit related to the question. However, my algorithm (neither the original version nor the slightly different revised version) is not so similar to ASort;. First, I believe my algorithm runs in $O(n)$, not in superlinear time like ASort. Second, criterion (\*) is pretty different from approximating Spearman's footrule distance; e.g., criterion (\*) is more or less tight depending on the values of the integers, unlike the footrule distance. Third, althout both our algorithm and ASort are bucketing elements, the criteria are pretty different.  
> **username_4**: @a3nm The clarification of what you posted above suggests you're using a **bucket sort**, which is linear (and not comparison-based, which means testing two items against each other). The problem is that it doesn't work for all mathematical integers. It only works if the integer size is bounded.  
> **username_0**: When you say "It only works if the integer size is bounded", I think this is only true if I were actually sorting the integers. But in general the algorithm I posted does not actually sort them, it only enforces the weaker criterion (\*). So I do think it runs in linear time even when the integer size is not bounded.  
> **username_4**: @a3nm It isn't linear. See my expanded response above.  
> **username_0**: Thanks for the answer, and sorry about the delay. I think there is some confusion about the model. I am working in the RAM model with uniform time measure (as in van Emde Boas, Machine Models and Simulations, in Handbook of Computation): so the numbers that I manipulate can have logarithmic size, but arithmetic operations on these numbers have unit cost. I have edited my question accordingly. I think that, in this model, the algorithm that I propose really runs in linear time (but of course in this model the $n \log n$ lower bound for actual comparison-based sorting still applies).  

---

