"Almost sorting" integers in linear time

Question

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<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
| +
+

This algorithm works as intended for the following reasons:

1. 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$

2. 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$.

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

   Let $j<n$ 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)<v$. 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<j+1$ or $k≤j$.

4. $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$.

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

Answer 1

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

Answer 2

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.

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