Consider a sequence $(s_1, ..., s_k)$, and we have it sorted in decreasing order $(\tilde{s}_1, ..., \tilde{s}_k)= (\sigma(s_1), ..., \sigma(s_k))$.
Define $k_{\max} = \max \left( \max_i \left( s_i - s_{i+1} \right), 0\right) $ and $k_{\max \text{sorted}} = \max \left( \max_i \left( \tilde{s}_i - \tilde{s}_{i+1} \right), 0\right) $ be the maximal decrease in consecutive elements.
Intuitively, $k_{\max \text{sorted}} < k_{\max} $. Any ideas how to prove it? (and how big is the gap between them?)
This isn't true. For instance, suppose your original sequence is in increasing order. Then $k_\max=0$, but $k_{\max \text{sorted}}>0$ unless all the terms are equal.
However, it is true (with a $\leq$ instead of $<$) if you assume either the first or the last number is already sorted, i.e. either $s_1=\tilde{s}_1$ or $s_k=\tilde{s}_k$. Let us suppose $s_k=\tilde{s}_k$; the other case is similar. Suppose that $k_{\max \text{sorted}}=\tilde{s}_i-\tilde{s}_{i+1}>0$, and $\tilde{s}_i=s_j$. Let $m$ be maximal such that $s_m\geq s_j$. Note that $j\leq m<k$, since $s_k=\tilde{s}_k<\tilde{s}_i=s_j$. By maximality of $m$, $s_{m+1}<s_j$. Since $\tilde{s}_{i+1}$ comes immediately after $\tilde{s}_i$ in the sorted sequence, this means that $s_{m+1}\leq \tilde{s}_{i+1}$. Thus $s_m-s_{m+1}\geq s_j-\tilde{s}_{i+1}=\tilde{s}_i-\tilde{s}_{i+1}=k_{\max \text{sorted}}$. We conclude that $k_\max\geq s_m-s_{m+1}\geq k_{\max \text{sorted}}$.