# 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?

• Which idea do you want to prove correct? Note that there is no single correct solution.
– Raphael
Feb 18, 2014 at 16:34
• Suppose the optimal solution had two pairs $(a, b)$ and $(A, B)$ with $a < A$ but $B < b$. Can you estimate the sum of differences? What if you swapped the $b$s? Feb 18, 2014 at 19:21

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