Minimum number of transpositions to sort a list In trying to devise my own sorting algorithm, I'm looking for the optimal benchmark to which I can compare it.  For an unsorted ordering of elements A and a sorted ordering B, what is an efficient way to calculate the optimal number of transpositions to get from A to B ?

A transposition is defined as switching the position of 2 elements in the list, so for instance

1 2 4 3


has one transposition (transposition 4 and 3) to make it

1 2 3 4


Something like

1 7 2 5 9 6


requires 4 transpositions (7, 2), (7, 6), (6,5), (9, 7)

Update (9/7/11): question changed to use "transposition" instead of "swaps" to refer to non-adjacent exchanges.
If you're only dealing with permutations of $n$ elements, then you will need exactly $n-c(\pi)$ swaps, where $c(\pi)$ is the number of cycles in the disjoint cycle decomposition of $\pi$. Since this distance is bi-invariant, transforming $\pi$ into $\sigma$ (or $A$ into $B$, or conversely) requires $n-c(\sigma^{-1}\circ\pi)$ such moves.