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