distance between sorted arrays Assume we have two arrays of real numbers:
$$
X = \{x_{1}, x_{2}, \dots, x_{n} \}
$$
and
$$
Y = \{y_{1}, y_{2}, \dots, y_{n} \}
$$
Next, assume that $d = \max(|x_{i} - y_{i}|)$. Next let us sort both arrays in increasing order:
$$
X'=\{x_{1}', x_{2}', \dots, x_{n}' \} = sort(X)
$$
and
$$
Y'=\{y_{1}', y_{2}', \dots, y_{n}' \} = sort(Y)
$$
Then, let $d' = \max(|x_{i}' - y_{i}'|)$.
Is it always $d' \leq d$?
 A: Look at the elements at positions 1 and 2 in both arrays.
$x_1, x_2$
$y_1, y_2$
If $x_1 > x_2$ swap these two.
If $y_1 > y_2$ swap these two.
Then move on to position 2 and do the same step/logic for
$x_2, x_3$
$y_2, y_3$
When you reach the end of the arrays, repeat this whole process (starting again at position 1) $n-1$ more times where $n$ is the length of the two arrays. I mean go through the arrays $n$ times in total.
Essentially I am describing an inefficient bubble sort here. That was Jaap's idea.
OK... after doing a single step (with potential swap done), we have 3 possible cases what happened:

*

*we swapped elements in both arrays,

*we didn't swap in any array,

*we swapped in just 1 of the arrays.

Can you prove that after this step the $d$ value decreases or stays the same?
I think that's quite obvious because in cases 1) and 2) the $d$ value stays the same, and in case 3) the $d$ value decreases (or again stays the same if the two values in the other array /the one whose elements we didn't swap/ are equal).
Why? Because if e.g. $x_k \gt x_{k+1}$ and $y_k \le y_{k+1}$ then $\max {|x_{k+1} - y_{k}|, |x_{k} - y_{k+1}|} \le \max {|x_k-y_k|, |x_{k+1}-y_{k+1}|}$
(i.e. the max after the swap $\le$ the max before the swap)
One can prove this separately as a small lemma.
So it seems that's the proof.
And your statement is indeed true.
