How can we minimize the total distance of cross pairs in an array
Let's follow Karolis's suggestion. Consider any solution with pairs $(a,b)$ and $(A,B)$ with $a \leq A$ and $B \leq b$, and write $A = a + \delta$, $B = b - \epsilon$. If we instead pair them $(a,B),(A,b)$, then instead of $|a-b|+|A-B|$ we get $|a-B|+|A-b|$. So we want to show
$$ |a-b|+|A-B| \geq |a-B|+|A-b|. $$
Substitute the expressions for $A,B$:
$$ |a-b| + |a-b+\delta+\epsilon| \geq |a-b+\epsilon| + |a-b+\delta|. $$
In terms of $C = a-b$, this is
$$ |C| + |C+\delta+\epsilon| \geq |C+\epsilon| + |C+\delta|. $$
Rearranging, this is the same as
$$ |(C+\delta)+\epsilon| - |C+\delta| \geq |C+\epsilon| - |C|. $$
So we need to look at the function $D \mapsto |D+\epsilon| - |D|$, whose values are
$$ |D+\epsilon| - |D| = \begin{cases} \epsilon &amp; D \geq 0, \\ 2D+\epsilon &amp; -\epsilon \leq D \leq 0, \\ -\epsilon &amp; D \leq -\epsilon \end{cases} $$
We see that this is an increasing function of $D$, and so $C+\delta \geq C$ implies the inequality we want,
$$ |(C+\delta)+\epsilon| - |C+\delta| \geq |C+\epsilon| - |C|. $$