0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Do you have any particular case in mind you want to ask about? If not, I don't think the question is ripe for an answer yet (you're basically asking us to invent some case that might be interesting, and then find an algorithm for it; but as we have no idea what you might find interesting vs not, that seems too vague/ill-specified to be usefully answerable). $\endgroup$ – D.W. Feb 11 at 23:43
  • $\begingroup$ I think the notation might be a tiny bit clearer if you numbered the sites and object $1..N$, so you write $h[a]$ and $m[i]$ and talk about site $a$ and object $i$ instead of $h[s_a]$ and $m[x_i]$ and site $s_a$ and object $x_i$. $\endgroup$ – D.W. Feb 11 at 23:43
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.