Here's what Math Reviews has to say: AUTHOR(S): Gates, William H. Papadimitriou, Christos H. TITLE: Bounds for sorting by prefix reversal. SOURCE: Discrete Mathematics 27 (1979), no. 1, 47--57. REVIEW: The authors study the problem of sorting a sequence of distinct numbers by prefix reversal -- reversing a subsequence of adjacent numbers which always contains the first number of the current sequence. Let f(n) denote the smallest number of prefix reversals which is sufficient to sort n numbers in any ordering. The authors prove that f(n) <= (5n+5)/3 by demonstrating an algorithm which never needs more prefix reversals. They also prove that f(n) >= 17n/16 whenever n is a multiple of 16. The sequences which achieve this bound are periodic extensions of the basic sequence 1, 7, 5, 3, 6, 4, 2, 8, 16, 10, 12, 14, 11, 13, 15, 9. If, furthermore, each integer is required to participate in an even number of prefix reversals, the corresponding function g(n) is shown to satisfy 3n/2 - 1 <= g(n) <= 2n+3. REVIEWER: Hwang, Frank K. (Murray Hill, N.J.)