Sorting on non-linear topology

Question

Disclaimer. What I'm going to ask about below may seem to be "Topological sorting". To my understanding, it is not. The latter runs in linear time, while I'm looking for a modification of the regular sort, which is at $N\log N$.

Remark. I'm doing the sort in the reverse order, to use the analogy with heights and masses.

Let us reformulate the sorting problem in the following way. Let us introduce two sets:

1. A set of sites (positions) $s_a,\,a=1..N$. Those are assigned certain 'heights' $h[s_a]$, which in the case of usual sorting can be simply $h[s_a]=a$.

2. A set of objects (numbers) $x_i,\,i=1..N$ which are assigned numerical values $m[x_i]$ (according to which the sorting will be performed). In the case of usual sorting, $m[x_i]$ are the numbers to be sorted.

The problem of sorting can be viewed as assigning to each object $x_i$ a site $s_a$ in such a way that for all assignments $\{x_i\to s_a; x_j\to s_b\}$: $$ h[s_a] > h[s_b] \Longrightarrow m[x_i]\leq m[x_j] $$

The physical visualization of this problem is a vertical stack of massive balls. Sorting them is equivalent to arranging them in such a way that heavier ones have lower height.

I first wanted to generalize the problem to "higher dimensions", i.e. to assume that the balls can stay in a $2$-dimensional grid, in a bucket, etc. However, I realized that from the computational point of view these settings are equivalent. In other words, whether we have a $2d$ grid with $nm$ balls in each row or a box with $n\times m$ balls in each layer makes no difference.

So, I decided to generalize the problem to an arbitrary topology (which can be reduced to the $2$-dimensional problem actually).

1. A set of sites (positions) $s_a,\,a=1..N$. Those are assigned certain 'heights' $h[s_a]$. Repetitions are allowed: $h[s_a]=h[s_b]$ for $a\neq b$ is OK.

2. A set of objects (numbers) $x_i,\,i=1..N$ which are assigned numerical values $m[x_i]$.

Again, we want to assign to each object a site in accordance with the same requirement as above.

Clearly, the brute-force solution for the most general set of 'heights' and 'masses' runs in $N \log N$. One simply sorts the objects according to their 'mass', and then fills the sites, starting from the 'highest' or the 'lowest' one.

Question. Has there been done any research for some particular cases? Clearly, if all the 'heights' are equal, the problem is trivial (which, I guess, means that it is solved in linear time). The first thing coming to my mind would be considering the case of "levels of same lengths", $$ h[s_a]=\lceil a/r\rceil,\,r\in\mathbb{N} $$ I would actually expect that this can be done faster than $N\log N$ (I'd assume that $r$ should enter the answer).

Answer 1

If there are $k$ distinct heights, you can sort in $O(n \log k)$ time using a heap or balanced binary tree. Even better, you can sort with expected time $O(n + k \log k)$, if you use a hashtable.

This leads to a solution to your problem with the corresponding complexity.