Minimization of difference

Question

Given two lists $\{a_1,a_2, \ldots,a_n\}$ and $\{b_1,b_2, \ldots,b_n\}$ and you can rearrange elements in each list individually. You have to rearrange element in it in such a way value of S is minimized.
$$ S = \sum_{i=1}^n \,\left| a_i-b_i\right| $$ What should be strategy of rearrangement of individual lists ?

Answer 1

Prove that sorting works for lists containing two elements: $\{a_1,a_2\}$ and $\{b_1,b_2\}$. Thus, you'll have proved that if $a_1\leq a_2$ and $b_1 \leq b_2$, then $|a_1-b_1|+|a_2-b_2| \leq |a_1-b_2|+|a_2-b_1|$. This proves it for lists of size $n$ as well - if there is an inverted pair, the SAD (sum of absolute differences) only decreases when you exchange elements of list b to remove inverted pairs.