Inequality involving rearrangement: $ \sum_{i=1}^n |x_i - y_{\sigma(i)}| \ge \sum_{i=1}^n |x_i - y_i|. $ If $x_1 \ge x_2 \ge \cdots \ge x_n$ and $y_1 \ge y_2 \ge \cdots \ge y_n$ are real numbers, and $\sigma$ is any permutation, then
$$
\sum_{i=1}^n |x_i - y_{\sigma(i)}| \ge \sum_{i=1}^n |x_i - y_i|.
$$
This must be a known inequality. What is it called, and how is it proven? (Just a reference is OK.)

The conditions are similar to rearrangement inequality. The inequality is a simple statement about minimizing the $\ell^1$ distance between a finite sequence and any rearrangement of another finite sequence.
I searched around and clicked through various pages but couldn't find something relevant. If it is true, perhaps a proof could be constructed by decomposing the permutation into a sequence of transpositions.

For any convex function, such as $f(x) = |x|$, 
$$ \sum f(x_i - y_{\sigma(i)}) \geq \sum f(x_i - y_i)$$
because $(x_i - y_{\sigma(i)})$ majorizes $(x_i - y_i)$.
A reference is the first theorem, 6.A.1, in chapter 6 of Olkin and Marshall's book on majorization, applied to the sequences $x_i$ and $-y_i$.  
They attribute the result to a 1972 article by Peter W Day on general forms of the rearrangement inequality, and give a proof for vectors of real numbers.  Day's article is about more general situations with ordered abelian groups.  The inequality for real vectors must have been known earlier to many people.
