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.

You may be interested in the following inequality.

Let $f_1, \dots, f_n: \mathbb{R} \rightarrow \mathbb{R}$ be functions such that for all $1 \leq k < n$
the function $f_{k+1} - f_k$ is non-decreasing. In addition, let $y_1 \geq y_2 \geq \dots \geq y_n$. Then,
$$
\sum_{k}f_k(y_{n-k+1}) \geq \sum_k f_k(y_{\sigma(k)}) \geq \sum_k f_k(y_k)
$$

The book "the cauchy-schwarz master class" does not give a formal name for this inequality but just call it "a non-linear rearrangement inequality". See p.81 of the book.

I show a proof based on the inequality above.

Proof. Let
$$
f_k(x) = |x_k - x|
$$
Then
$$
f_{k+1}(x) - f_k(x) =
\begin{cases}
x_{k+1}-x_{k} &\text{if}\ x \leq x_{k+1} \\
2x - x_{k+1} - x_k &\text{if}\ x_{k+1} < x < x_k\\
x_{k} - x_{k+1} &\text{otherwise}
\end{cases}
$$
is non-decreasing, thus the inequality applies. That is,
$$
\sum_k |x_k - y_k| \leq \sum_k |x_k - y_{\sigma(k)}| \leq \sum_k |x_k - y_{n-k+1}|
$$

