How can we minimize the total distance of cross pairs in an array

Suppose we had 2 arrays of the same size with positive numbers and we wanted to pair up the elements of each array such that the total difference between the pairs is minimized.

The first thought would be to choose pairs with the minimum difference and so on. But it turns out the correct algorithm is to sort them and them pair accordingly.

Any ideas on how to prove that the latter algorithm correctly minimizes the sum of differences?

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 & D \geq 0, \\ 2D+\epsilon & -\epsilon \leq D \leq 0, \\ -\epsilon & 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|. $$

StackExchange Computer Science Q#21767, answer score: 2