As a lower bound, you can have a look at this joint paper with Christos Papadimitriou from 1976: http://www.cs.berkeley.edu/~christos/papers/Bounds%20For%20Sort

As a lower bound, you can have a look at this joint paper with Christos Papadimitriou from 1976: http://www.cs.berkeley.edu/~christos/papers/Bounds%20For%20Sorting%20By%20Prefix%20Reversal.pdf http://www.cs.berkeley.edu/~christos/papers/Bounds%20For%20S...