Maximum number of letter swaps required to unscramble an n-letter word. This must be a simple question, but surprisingly, I can't find an answer by googling. 
What is the maximum number of letter swaps M(n) required to unscramble an n-letter word?
By letter swaps I mean swapping letters at positions i and i+1. The n-th letter swaps with the first letter.
I guess a recursive formula would be:
M(1)=0 
M(n) = M(n-1) + (n - 1)
Assuming this is correct, what would be a non-recursive formula? 
 A: This is a partial answer, giving upper and lower bounds on $M(n)$.
I will be using numbers instead of letters, because the mathematical problem isn't really concerned with words, and "$123$" is easier to recognize as the "target" of the swapping than any natural word.
For clarity (it seemed to have confused a few commentors): Swapping the letter at the $n$-th position and the first position is allowed in the procedure. I'll call this the "round table procedure" (because it mimics $n$ persons sitting around a round table and they can only move if 2 neighbours swap their places).
The standard way to consider this problem is not allowing the $n$-th position and the first position to be able to be swapped for $n > 2$ (the "standard procedure"). Let's call the maximum number of swaps necessary using  this standard procedure $S(n)$. Then it is well known that for $n \ge 1$
$$S(n)=\frac{n(n-1)}2 = 1+2+\ldots+(n-1).$$
You can swap the "$1$" to the first position in at most $n-1$ swaps (it takes $i-1$ swaps from position $i$), then, without disturbing the "$1$" any further, you can swap the "$2$" to the second position in at most $n-2$ swaps, a.s.o. That shows it can be done in the number of moves given above. In addition, it can be shown that when you start with the numbers completely reversed as "$n(n-1)\ldots321$", you cannot do with less.
A first insight into the round table procedure is that you can get any number to any desired position in at most $\lfloor\frac{n}2\rfloor$ swaps. That's because if a number is currently in position $i$ an should go to position $j$, you need $|i-j|$ swaps in the standard procedure (which of course also works in the round table procedure), but you can also go through the swap of position $1$ and $n$, which takes $n-|i-j|$ swaps. The round table analogy helps here, you have 2 ways around the table from position $i$ to $j$, and their length add up to $n$. That means the shorter way is at most $\frac{n}2$ swaps long, and since it must be an integer, it follows it is at most $\lfloor\frac{n}2\rfloor$.
This gives a (slightly better) upper bound for $M(n), n \ge 2$:
$$M(n) \le \lfloor\frac{n}2\rfloor + S(n-1),$$
because you can swap the "$1$" into the first position using at most $\lfloor\frac{n}2\rfloor$ swaps, then use the standard procedure on the remaining $n-1$ numbers to order them all, without swaping the "$1$" away from the first position any more. The reason we have to revert to the standard procedure after getting the "$1$" into its correct position is that the "short way" to get the "$2$" into its correct position might swap the "$1$" away from its position, so we need add more swaps to get the "$1$" back to where it is wanted, which makes it hard to get a good upper bound.
Using the above formula for $S(n-1)$, we get
$$M(n) \le \frac{(n-1)(n-2)}2 + \lfloor\frac{n}2\rfloor$$
Considering that 
$$S(n)= \frac{(n-1)(n-2)}2 + (n-1),$$
the upper bound is only decreased by $\approx \frac{n}2$.
To get a lower bound, consider the target word shiftet by $\lfloor\frac{n}2\rfloor$ to the right as the starting word, that would be
$$s_e=(\frac{n}2+1)(\frac{n}2+2)\ldots(n-1)n12\ldots(\frac{n}2-1)(\frac{n}2),$$
for even $n$ and similarly for odd $n$
$$s_o=(\frac{n+1}2)(\frac{n+3}2)\ldots(n-1)n12\ldots(\frac{n-3}2)(\frac{n-1}2).$$
Each number in $s_e$ and $s_o$ is at the same minimum swapping distance to its target position as any other number, $\frac{n}2$ and  $\lfloor\frac{n}2\rfloor=\frac{n-1}2$, resp.
That means to get either starting word to the target word "$123\ldots(n-1)n$", each number must be swapped  $\lfloor\frac{n}2\rfloor$ times at least. Since we have $n$ such numbers, and each swap moves just 2 numbers, we see that for those 2 words the number of required swaps is at least
$$\frac{n\lfloor\frac{n}2\rfloor}2,$$
which means we get the following lower bound:
$$M(n) \ge \left\lceil\frac{n\lfloor\frac{n}2\rfloor}2\right\rceil.$$
Again ignoring the floor/ceiling functions the lower bound for $M(n)$ is of magnitude $\frac{n^2}4$, which is half of the of value of $S(n)$.

I have no idea where the true value of $M(n)$ will be: Asymptotically $\frac{n^2}4$ or $\frac{n^2}2$, or even something in between? I'd welcome any additions that give better insight into the nature of $M(n)$ and its upper and lower bounds.
