Let $(X,\leq)$ be a totally ordered set. A sort for $f\in X^n$ is an element $g\in X^n$ satisfying
(i) $g$ is nondecreasing.
(ii) $ g=f\circ \sigma$ for some permutation $\sigma:\{1,\dots,n\}\to \{1,\dots,n\}$.
A sorting function for $X^n$ is a function $\Phi:X^n\to X^n$ such that $\Phi(f)$ is a sort for $f$, for each $f\in X^n$.
Am asked to show that there exists a sorting function for $X^n$.
My attempt:
By induction on $n$. If $n=1$ this is trivial. Suppose there exists a sorting function $\Phi:X^n\to X^n$ for some $n\geq 1$.
Define the functions $\Gamma,\Delta:X^{n+1}\to X^{n+1}$ by $$\Gamma(f)=\bigg(\Phi[f|_{\{1,\dots,n\}}],f(n+1)\bigg)$$
$$\Delta(f)=f\circ \pi$$
where $\pi:\{1,\dots,n+1\}\to \{1,\dots,n+1\}$ is the permutation defined by
$$\pi(i)=\begin{cases} i & \text{if } \quad i<i_0 \\ n+1 & \text{if } \quad i=i_0 \\ i-1 & \text{if } \quad i>i_0 \end{cases}$$
where $i_0$ is the smallest element of the set $\big\{1\leq i\leq n:f(n+1)\leq f(i)\big\}$ if this set is nonempty, and $i_0:=n+1$ otherwise.
I claim that $\Phi':=\Delta\circ \Gamma$ is a sorting function for $X^{n+1}$. Since $\Phi[f|_{\{1,\dots,n\}}]=f|_{\{1,\dots,n\}}\circ \sigma$ for some permutation $\sigma:\{1,\dots,n\}\to \{1,\dots,n\}$ we see that $\Gamma(f)=f\circ \sigma'$ for some permutation $\sigma'$. Then
$$\Phi'(f)=(\Delta\circ \Gamma) (f)=f\circ \sigma'\circ\pi$$ for the permutation $\sigma'\circ\pi$. By considering the different cases with respect to $i_0$ we also see that $i\leq j$ implies $\Phi'(f)(i)\leq \Phi'(f)(j)$. Hence $\Phi'(f)$ statisfies (i) and (ii) for all $f\in X^{n+1}$ and so is indeed a sorting function for $ X^{n+1}$.
Is this correct?
Thanks a lot for your help
As far as I can tell it seems correct, however, I am not totally sure since I find it a bit convoluted. I think the proof becomes more concise using $\max$ instead of the smallest element that is larger than $f(n+1)$.
Let $[n]:=\{1,\dots,n\}$ and $\text{argmax}_n(f):=\max f^{-1}(\max\{f(i):i\in[n]\})$ for all $n\in\mathbb{N}$ and $f\in X^n$. Now, proving via induction: as you wrote, the base case is trivial.
Suppose there exists a sorting function $sort_n$ for $X^n$ for some $n\geq1$. For every $f\in X^{n+1}$ define $\pi_f:[n+1]\rightarrow[n+1]$ such that $$\pi_f(k)=\begin{cases}n+1&\text{if }k=\text{argmax}_{n+1}(f)\\\text{argmax}_{n+1}(f)&\text{if }k=n+1\\k&\text{otherwise}\end{cases}$$ Also, for every $f\in X^{n+1}:\exists\sigma_f:[n]\rightarrow[n]$ such that $$sort_n(f|_{[n]})=f|_{[n]}\circ\sigma_f$$ Also, define for every $\sigma:[n]\rightarrow[n]$ the unique permutation $\sigma^*:[n+1]\rightarrow[n+1]$ such that $\sigma^*|_{[n]}=\sigma$.
Now define $sort_{n+1}(f):X^{n+1}\rightarrow X^{n+1}$ such that $$sort_{n+1}(f)=f\circ\pi_f\circ\sigma_{f\circ\pi_f}^*$$
(EDIT: as has been pointed out in the comments: This is well-defined since although the permutation $\sigma_{f\circ\pi_f}^*$ isn't necessarily unique, the permutations only differ if there are mutliple elements which are the same which can be arbitrarily exchanged with eachother, however as equal elements are swapped, the result stays the same.)
Now, it is clear that $sort_{n+1}(f)|_{[n]}=sort_n(f\circ\pi_f|_{[n]})$, for which it is clear, that it is non-decreasing via induction hypothesis. It is also clear that $sort_{n+1}(f)(n+1)$ is the maximum via definition. Therefore, the whole element is non-decreasing. And since permutations are closed under composition, $sort_{n+1}$ is indeed a sorting function.