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

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!

• First making a list of pairs and then sorting that list seems to be $O(n^2\log n)$, at least naively (even if you're clever enough to first make all pairs that contain $1$ as the smallest number, then all pairs with $2$, and so on; you will have a bunch of the sorting job already done, but I don't think there is any significantly clever way of sorting them afterwards). Nov 15 '19 at 16:30
• yup so you can easily make $n$ lists all sorting already. Still stuck to merge them. It kind of skipping the first half of the job with merge sort but I still got $O(\frac{1}{2}n^2logn)$ job to do
– Shaq
Nov 15 '19 at 16:35
• I'd imagine a sweep would work in $O(n^2)$ (but I haven't fully worked out the algorithm or thought through this very carefully). If your sorted list of numbers is $x_1 < x_2 < \dots < x_n$, then make lists of the end differences $$0 = x_1-x_1 < x_2-x_1 < x_3-x_1 < \dots < x_{n-1} - x_1 < x_n-x_1$$ $$x_n - x_1 > x_n - x_2 > x_n - x_3 > \dots > x_n - x_{n-1}> x_n-x_n = 0$$ Then peel off end differences, removing as small a difference as possible Nov 15 '19 at 18:43
• I thought also in that direction. I think it might be the right way but I can't organize the inequalities and solve the puzzle.
– Shaq
Nov 15 '19 at 19:34

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

• It does make sense what you propose. I was never sure it is possible. It was a bit hard for me to track all your answer, but if X+Y sorting is an open problem, this one doesn't sound very far away from it. Thank you very much for your help. It is reasonable to believe it is not possible.
– Shaq
Nov 21 '19 at 11:23

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.

• its true, but if $k=n^3$ than the algorithm is not helpfull
– Shaq
Nov 15 '19 at 16:58
• There is no way to solve it without using the fact that your list is compound out of pairs of a smaller list
– Shaq
Nov 15 '19 at 16:59
• Indeed, when $k$ is big this algorithm is useless. I still found it worth mentioning. Nov 15 '19 at 17:01