Least permutations needed to permute from decreasing order to increasing order You are asked to permute the neighboring sub-sequence of the sequence $n,n-1,n-2,\cdots,1$ until the sequence is brought to the increasing order.  
By permute the neighboring sub-sequence I mean for example:
$5,4,3,2,1 \to 5,3,4,2,1 $ or $5,4,3,2,1\to 5,2,4,3,1$ or $5,4,3,2,1\to5,2,1,4,3$. 
What is the least number of permutations needed?
Edit
A first nontrivial case I can come up with is:
$$
54321\to52143\to14523\to12345
$$
Edit 2
A second nontrivial case I come up with to show $T(n)<f(n)$ is possible regarding the answer by @Brian M. Scott:
$$
7654321\to7632154\to7215634\to1567234\to1234567
$$
maybe $\frac{n+1}{2}$?
 A: You need at least $\lceil (n+1)/2\rceil.$ Consider the number $G$ of terms whose right neighbor is greater. $G$ starts at zero and ends as $n-1.$
For example
$$G(5,4,3,2,1)=0$$
$$G(5,2,1\color{red},4,3)=1$$
$$G(1\color{red},4\color{red},5,2\color{red},3)=3$$
$$G(1\color{red},2\color{red},3\color{red},4\color{red},5)=4$$
I have colored in red the comma between each term and its right neighbour whenever that neighbour is greater.
By Brian M. Scott's definition given in the comments, each swap is of the form $WXYZ\to WYXZ$ where $W,X,Y,Z$ are possibly empty subwords. Let $q,r,s,t$ be the lengths of $W,X,Y,Z$ respectively. Let
$$w_1,\dots,w_q,x_1,\dots,x_r,y_1,\dots,y_s,z_1,\dots,z_t=WXYZ$$
so
$$w_1,\dots,w_q,y_1,\dots,y_s,x_1,\dots,x_r,z_1,\dots,z_t=WYXZ.$$
For example for $5,4,3,2,1\to 5,2,1,4,3$ we have $(q,r,s,t)=(1,2,2,0).$
Note
\begin{align*}
G(WYXZ)-G(WXYZ)=[w_q<y_1]+[y_s<x_1]+[x_r<z_1]\\-[w_q<x_1]-[x_r<y_1]-[y_s<z_1]\tag{1}
\end{align*}
where $[a<b]=1$ if $a<b$ and $[a<b]=0$ otherwise (Iverson bracket notation). If $q=0$ ignore the terms using $w_q,$ and if $t=0$ ignore the terms using $z_1.$
We can write the entire sequence of swaps as $P_0\to P_1\to \dots\to P_m$ where $m$ is the number of swaps, and $P_0=(n,n-1,\dots,1),$ and $P_m=(1,2,\dots,n).$
In the first swap $WXYZ=P_0\to P_1=WYXZ,$ we always have $w_q>y_1$ and $x_r>z_1.$ So by (1) we must have $G(P_1)-G(P_0)\leq 1.$ 
In the final swap $WXYZ=P_{m-1}\to P_m=WYXZ$ we always have $w_q<x_1$ and $y_s<z_1,$ so $G(P_m)-G(P_{m-1})\leq 1.$
Now consider an arbitrary swap $WXYZ=P_{i}\to P_{i+1}=WYXZ.$ From (1) we know $G(P_{i+1})-G(P_i)\leq 3,$ and it cannot be exactly $3$ because that would give $w_q<y_1<x_r<z_1<y_s<x_1<w_q.$ So $G(P_{i+1})-G(P_i)\leq 2.$ To summarize:
\begin{align*}
&G(P_{1})&-&&&G(P_0)&\leq 1\\
&G(P_{i+1})&-&&&G(P_i)&\leq 2&\qquad\text{ for }1\leq i\leq m-2\\
&G(P_{m})&-&&&G(P_{m-1})&\leq 1
\end{align*}
which sum to $n-1=G(P_m)-G(P_0)\leq 2m-2.$ So $m\geq\lceil (n+1)/2\rceil.$
A: $n-1$ is an upper bound as we can exhibit an algorithm that achieves that.  Take successive pairs of elements and invert them.  This uses $\lfloor \frac n2 \rfloor$ swaps.  Lock together the pairs you have swapped, considering the pair to be one element, and you have $n-\lfloor \frac n2 \rfloor=\lceil \frac n2 \rceil$ elements left.  Now use the same algorithm again.  Repeat until you have only one element left, which means the list is in proper order.  
Let $T(n)$ be the number of swaps needed for a list of length $n$.  $T(1)=0, T(2)=1$ are the base cases for induction.  Assume $T(k)=k-1$ has been proven up to $k$.  Then $T(k+1)=\lfloor \frac {k+1}2 \rfloor + T(\lceil \frac {k+1}2 \rceil)=\lfloor \frac {k+1}2 \rfloor + \lceil \frac {k+1}2 \rceil-1=k$
A: 
A detailed canonical answer is required

As far as I understood, you are asking about a minimal number $d(\iota)$ of transpositions (swaps of adjacent blocks) required to sort (that is, transform to identity) the completely reverted permutation $\iota$. It equals $\lceil (n+1)/2\rceil$ for $n\ge 3$, see Theorem 4.2 in [EEKSW]. This is a known special case of a general well-studied problem called Sorting by Transpositions in computational biology for DNA sequences introduced by Bafna and Pevzner [BP] in 1995 and shown to be NP-hard by Bulteau et al. [BFR] in 2010. See [FLRTV] for a detailed review on this problem and its variants and refer to [S, ES, MS , DMW] for more background on genome rearrangements. A number of studies designs approximation algorithms and bounds for $d(\pi)$, see the beginning of [BFT] for related references. For instance, Eriksson et al. [EEKSW] provided an algorithm that sorts any given permutation on $n$ elements by at most $2n/3$ transpositions. On the other hand, as far as I know, no tight upper bound for the necessary number of steps in Sorting by Transpositions is known. The best-known ﬁxed-ratio algorithm being a 1.375-approximation [EH]. 
References
[BFR] Laurent Bulteau, Guillaume Fertin, Irena Rusu, Sorting by Transpositions Is Difficult, SIDMA, 26:3 (2012), 1148-1180, arXiv version.
[BP] V. Bafna and P. A. Pevzner, Sorting permutations by transpositions, in Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995, 614–623.
[DMW] Z. Dias, J. Meidanis, M. E. Walter Reversal and transposition distance of linear chromosomes. In: String Processing and Information Retrieval: A South American Symposium (SPIRE 98), 1998.
[EEKSW] H. Eriksson, K. Eriksson, J. Karlander, L. Svensson, J. Wästlund, Sorting a bridge hand, Discrete Math. 241:1 (2001), 289-300.
[EH] I. Elias, T. Hartman, A 1.375-approximation algorithm for sorting by transpositions, IEEE/ACM Trans Comput. Biol. Bioinform., 3:4, 369-379, 2006. doi:10.1109/TCBB.2006.44.
[ES] N. El-Mabrouk,  D. Sankoff, Genome rearrangement. In: T.Jiang, T. Smith, Y. Xu, and M. Q. Zhang, editors, Current Topics in Computational Molecular Biology. MIT Press, 2002.
[FLRTV] G. Fertin, A. Labarre, I. Rusu, É. Tannier, S. Vialette, Combinatorics of Genome Rearrangements, The MIT Press, Cambridge, MA, 2009.
[MS] J. Meidanis, J. Setubal. Introduction to Computational Biology. PWS Publishing Co., 1997.
[S] R. Shamir. Algorithms in molecular biology: Lecture notes, 2002.
A: I don’t know that it’s best possible, but I can show that if $T(n)$ swaps are needed to reverse $\langle n,n-1,\ldots,1\rangle$, then $T(n)\le\left\lfloor\frac{3n}4\right\rfloor$. For convenience let $f(n)=\left\lfloor\frac{3n}4\right\rfloor$. It’s not hard to verify that $T(1)=0=f(1)$, $T(2)=1=f(2)$, $T(3)=2=f(3)$, and $T(4)=3=f(4)$, and the OP has shown that $T(5)=3=f(5)$.
Now suppose that $n>5$, and $T(k)\le f(k)$ for $k<n$. Let $n=4q+r$, where $r\in\{0,1,2,3\}$ and $q\ge 1$. In $3$ swaps the initial sequence can be transformed into 
$$\sigma=\langle n-4,n-3,n-2,n-1,n,n-5,n-6,\ldots,2,1\rangle\;.$$
Now treat the first $5$ terms of $\sigma$ as a single entity $\widehat{n-4}$ and work with the sequence
$$\hat\sigma=\left\langle\widehat{n-4},n-5,n-6,\ldots,2,1\right\rangle$$
of length $n-4=4(q-1)+r$. The induction hypothesis says that 
$$T(n-4)\le f(n-4)=3(q-1)+f(r)\;,$$
so $\hat\sigma$ can be transformed into 
$$\left\langle 1,2,\ldots,n-5,\widehat{n-4}\right\rangle=\langle 1,2,\ldots,n-5,n-4,n-3,n-2,n-1,n\rangle$$
with $3(q-1)+f(r)$ further switches. Thus,
$$T(n)\le 3+3(q-1)+f(r)=3q+f(r)=f(n)\;,$$
and the induction is complete.
Added: This can definitely be improved. For a string $\langle a_1,\ldots,a_n\rangle$ and $1\le i<j\le k\le n$ let $S(i,j,k)$ be the operation of swapping the substrings $\langle a_i,\ldots,a_{j-1}\rangle$ and $\langle a_j,\ldots,a_k\rangle$. If $n=2m+1$, perform the swaps $S(k,k+2,k+m+1)$ for $k=m,m-1,\ldots,1$, then perform $S(2,m+1,n)$. Then:


*

*$a_n=1$ moves $2$ places to the left $m$ times, putting it in position $1$ where it stays on the last move;  

*$a_{n-1}=2$ moves $2$ places to the left $m-1$ times, reaching position $2$, then $S(2,4,m+3)$ moves it to position $m+2$, and the final swap moves it back to position $2$;  

*in general for $k=0,\ldots,m-1$, $a_{n-k}=k+1$ moves $2$ places to the left $m-k$ times to reach position $k+1$, then moves to position $m+k+1$ with $S(k+1,k+3,m+k+2)$, where it remains until the final swap moves it back to position $k+1$;  

*$a_{m+1}=m+1$ is sent by the first swap to position $n$, where it stays until the final swap moves it back to its original position;  

*for $k=2,\ldots,m$, $a_k=n+1-k$ stays in its original position for the first $m-k$ swaps, at which point it moves $m$ places to the right to position $m+k$, after which it moves left $2$ places with each of the remaining $k-1$ swaps before the final one, reaching position $m-k+2$, and the final swap takes it to position $2m-k+2=n+1-k$; and  

*$a_1=n$ stays in its original position for the first $m-1$ swaps, then moves to position $m+1$ and thence to position $2m+1=n$ with the final two swaps.


Thus, $T(2n+1)\le m+1$. 
It’s not hard to check that if $n=2m$, the swaps $S(k,k+2,k+m+1)$ for $k=m-1,\ldots,1$ followed by $S(1,2,2)$ and $S(3,m+2,2m)$ will convert $\langle 2m,\ldots,1\rangle$ to $\langle 1,\ldots,2m\rangle$, so $T(2m)\le m+1$, and in general we have
$$T(n)\le\left\lceil\frac{n+1}2\right\rceil\;.$$
