Looking for a sorting algorithm in $O(n)$ with some assumptions

Question

So I am looking for an algorithm that can help me with a task.

I have $n$ Natural (positive intiger) numbers. I want to make a list of their pairs.

There are $n\choose2$ pairs, which is $O(n^2)$.

I want to make a list of these pairs by the absolute value of the subtraction.

so for example if my list is $(1,2,4,9)$ the output result would be:

$((1,2),(2,4),(1,4),(4,9),(2,9),(1,9))$

I am looking for an algoritm that would do so in $O(n^2)$. You can assume the list

is sorted at the beginning, any way its a matter of only $O(nlogn)$.

Thanks a lot!

Answer 1

It is (probably) not possible to do better than $O(n^2 \log\ n)$ in the worst case. To see why, let us first look at the information we have about the input that could help us. We know that of the elements we want to sort, all intervals [$x$, $y$], some orderings are already given. That is, we know that if $x_1$ < $x_2$ < $x_3$ then [$x_1$,$x_3$] > [$x_1$,$x_2$] and [$x_1$,$x_3$] > [$x_2$,$x_3$]. So what we have is a poset of intervals where every interval is ordered by inclusion. The worst case complexity of sorting a poset is $O(\log\ L(n))$ where $L(n)$ is the number of linear extensions of the poset. And how many linear extensions are there for our situation? I used Sage to calculate the number of linear extensions for some small values, starting with $n$=3:

2, 16, 768, 292864, ...

This seems to be the sequence A005118. I unfortunately haven't found a way to prove that yet. But if we assume that $L(n)$ follows the sequence then we have the closed form $$ L(n)=\frac{{n \choose 2}!}{\prod_{i=0}^{n-2}(2*i + 1)^{n - i - 1}}. $$

Then we have $$ \log(L(n))=\log\left(\frac{{n \choose 2}!}{\prod_{i=0}^{n-2}(2*i + 1)^{n - i - 1}}\right) \in \Theta\left(n^2*\log(n)\right) $$ $$ \implies O(\log L(n)) = O(n^2\log\ n) $$

so our algorithm can not be better than $O(n^2 \log\ n)$.

Edit: This is under the Decision tree model of computation. Other analysis could be done under other models. I think this is a pretty hard problem in general, given that it is reminiscent of X + Y sorting for which it is an open problem to find algorithms faster than $O(n^2 \log\ n)$.

Answer 2

If you know the minimum and maximum values of a list of $n$ integers, you can sort them in $O(n+k)$ time using Counting sort, where $k$ is the maximum element. You can determine the minimum and maximum in linear time.