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

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