Block Sorting and Sorting with Transpositions

is to use the fewest possible moves.

If any substring can be chosen and can be moved anywhere, the status
of the problem is open. (in P? NP-hard?) There is a 3/2 approximation
algorithm.

If the substring must be a block (a maximal substring of the sorted
permutation), and must move to merge with another block, then
the problem is NP-hard, and has a 2 approximation algorithm (which
even runs in NC).

If the substring must be a single element, and can move just one or
two locations away, then the status of the problem is open. There is a
4/3 approximation algorithm. (If the substring must be a single
element, and can move just one location away, then bubblesort
optimally sorts the input.)

The talk surveys these results and highlights open problems.