Bill Gates published one academic paper on sort. You are given an array A of unsorted integers and the only allowed operation is to "flip" a sub-array. A flip(i) is an operation which reverses all the sub-array starting in position A[i]. Namely,
(A, .... A[i-1], A[i], A[i+1] ...., A[n-1], A[n])
is changed into
(A, .... A[i-1], A[n], A[n-1] ...., A[i+1], A[i])
Can you suggest a sorting algorithm based just on flip() operations?
PS: this sorting method has an impact on genetic studies and evolution of species.
PS: the paper is W. Gates and C. Papadimitriou, Bounds for sorting by prefix reversal (1976)