An algorithm to turn descending order into ascending order, but why correct?
This is an interesting algorithm.

Conventions

Array indexes start with 0. Note this convention is different from the convention used in the question. This convention helps us see what is going on more easily.

All arrays have length $n=2^m$ for some positive integer $m$.

Given any array $b_0, b_1, b_2, b_3,\cdots, b_{n - 2}, b_{n-1}$, the magic shuffle $M$ maps it to the array $b_1, b_3, \cdots, b_{n-1}, b_0, b_2, \cdots, b_{n-2}.$ Please note that I avoid using the term "sort" since this algorithm is hardly about sorting.

Let $A_0$ be the array $a_0, a_1, \cdots, a_{n-1}$ (that is, $A_0[i]=a_i$). Define $A_k$ recursively by $A_{k+1}= M(A_k)$.

Claim: $A_m$ is the reverse of $A_0$, which is $a_{n-1}, a_{n-2}, \cdots, a_0$.

Proof of the claim. For an array $B$, we can check by the definition of the magic shuffle, $$M(B)[i] = \begin{cases} B[2i+1] &amp; \text{ if }i\lt 2^{m-1},\\
B[2(i-2^{m-1})]&amp;\text{ if } i\ge 2^{m-1}.\end{cases}$$

For an integer $i=i_{m-1}2^{m-1} + i_{m-2}2^{m-2} + \cdots + i_12 + i_0$, where $i_t\in\{0,1\}$, let $(i_{m-1}i_{m-2}\cdots i_1i_0)_2$ be its representation in base 2. We can easily check that

$$M(B)[(i_{m-1}i_{m-2}i_{m-3}\cdots i_1i_0)_2] = B[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2]$$
where $\overline{x}=1-x$ for $x=0,1$. So we have
$$A_1[i] = M(A_0)[i] = A_0[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2]$$
$$A_2[i] = M(A_1)[i] = A_1[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2] = A_0[(i_{m-3}\cdots i_1i_0\overline{i_{m-1}}\overline{i_{m-2}})_2]$$
$$\cdots$$
$$A_{m-1}[i] = M(A_{m-2})[i] = A_{m-2}[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2] = A_0[(i_0\overline{i_{m-1}}\overline{i_{m-2}}\cdots\overline{i_2}\overline{i_1})_2]$$
$$A_m[i] = M(A_{m-1})[i] = A_{m-1}[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2] = A_0[(\overline{i_{m-1}}\overline{i_{m-2}}\cdots\overline{i_2}\overline{i_1}\overline{i_0})_2]$$

Since $i + (\overline{i_{m-1}}\overline{i_{m-2}}\cdots\overline{i_1}\overline{i_0})_2 = (\overline1\overline1\cdots\overline1\overline1)_2 = n-1$, we have proved the claim.

An exercise

Let $a_0, a_1, \cdots, a_{n-1}$ be an array of length $n=2^m$ for some positive integer $m$. For each step from 1 to m, repeat the following shuffle. For each term in the front half of the array, insert right before it the $n/2$-th term after it. Here is the result array after each shuffle for $n=16$.

[0]  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16  
[1]  9  1 10  2 11  3 12  4 13  5 14  6 15  7 16  8  
[2] 13  9  5  1 14 10  6  2 15 11  7  3 16 12  8  4  
[3] 15 13 11  9  7  5  3  1 16 14 12 10  8  6  4  2  
[4] 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  


Show that we will obtain the initial array reversed in the end of $m$ shuffles. 

If you consider the array as a deck of cards, then this shuffle is the (perfect) in (riffle) shuffle. In particular, if you repeat 10 in shuffles on a deck of 32 cards, you will end up with the deck of cards in its original order.