Say suppose $x,y \in \mathbb{R}^n$. Assume we have a sorting algorithm that sort $x \to X: \{ x_i \}_{i=1}^n = \{ X_i \}_{i=1}^n $
and for every $1 \leq i \leq j \leq n$, $X_i \leq X_j$.
The same thing applies to $Y$.
Is it true that $||X-Y||_2^2 \leq ||x-y||_2^2$ ? If yes, prove it. If not, give a counterexample.
Many thanks!
p/s: here is what I got so far: equivalent transformation
$\sum_{i=1}^n (X_i -Y_i)^2 \leq \sum_{i=1}^n (x_i -y_i)^2$
We have $\sum_{i=1}^{n}(X_i - Y_i)^2 \leq \sum_{i=1}^{n}(x_i - y_i)^2 \iff X_1Y_1 + ... + X_nY_n \geq X_1Y_{\sigma(1)} + ... + X_nY_{\sigma(n)}$ after some expansion and rearrangement, where $\sigma$ represents the permutation of $[n]$ corresponding to the unsorted lists. More specifically, we let $\sigma$ be such that $\forall k \in [n]$, $(X_k, Y_{\sigma(k)})$ is equivalent to a unique pair $(x_i,y_i)$. $X_1Y_1 + ... + X_nY_n \geq X_1Y_{\sigma(1)} + ... + X_nY_{\sigma(n)}$ follows immediately from the rearrangement inequality (see: https://en.wikipedia.org/wiki/Rearrangement_inequality), since $X_1 \leq ... \leq X_n$ and $Y_1 \leq ... \leq Y_n$.