Can you outgolf Bill Gates?

Question

Pancake sorting is the colloquial term for the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number P(n) is the minimum number of flips required for n pancakes. 1

In 1979, a young Bill Gates and Christos Papadimitriou, wrote a paper proving an upper bound of P(n) = (5n+5)/3. 2

I think it's safe to assume that Gates (and/or Papadimitriou) wrote a program to perform pancake sorting using the algorithm they developed (possibly later than 1979). Since Gates was a skilled programmer, they probably tried to golf this code as well as they could, but the size of the source code is not publicly available (AFAIK).

Challenge:

Create a function / program that performs pancake sorting, where the maximum number of flips doesn't exceed the bound found by Gates and Papadimitriou.³ You may choose if you want the list ascending or descending, as long as it's consistent.

You may assume that n < 50. You must therefore limit the number of flips to (some randomly selected n-values):

 n   P(n)
38   65
49   83
50   85

The output should be the position of the spatula before each flip. The output may be zero or one-indexed, and you may choose if you count from the top or bottom.

Additional rules:

• The runtime must be deterministic
• There is no fixed time limit, but you must be able to provide the output for a list with 50 elements

Test lists:

I can't provide the hardest lists (if so, I would write a paper, not a challenge), so I'll provide some random lists of numbers you can test your functions/programs on. I might add others if it turns out these lists where "easy".

9, 63, 62, 75, 45, 78, 59, 75, 69, 3, 28, 94, 51, 10, 45, 93, 97, 80, 72, 36, 80, 88, 30, 93, 84, 80, 17, 31, 6, 80, 76, 91, 9, 76, 38, 33, 22, 15, 45, 46, 15, 98, 2, 56, 90, 27, 27, 26, 69, 25
...
74, 89, 57, 52, 70, 96, 16, 5, 77, 84, 54, 13, 90, 64, 31, 80, 3, 25, 13, 19, 13, 34, 1, 79, 35, 43, 4, 19, 82, 29, 48, 95, 97, 28, 45, 62, 64, 82, 70, 34, 38, 15, 51, 83, 21, 66, 4, 42, 74, 84
...
62, 73, 7, 90, 83, 18, 12, 35, 72, 71, 99, 67, 87, 62, 65, 70, 14, 72, 55, 92, 87, 3, 7, 4, 4, 95, 49, 25, 4, 18, 49, 39, 26, 1, 45, 64, 23, 66, 39, 17, 33, 24, 58, 72, 77, 46, 99, 71, 10, 21

---

Hopefully, Bill Gates and Papadimitriou will see this challenge, and provide their code, so that we can determine if you did in fact outgolf them.

_{³Better upper bounds have been found, but you do not need to care about those.}

Answer 1

Python 2 (PyPy), 238 235 222 bytes

a=input();n=len(a);r=range(n);a=zip(a,r);a=map(sorted(a).index,a)+[n]
def s(u,m):
 if m<1:return[0]
 for k in r:
  v=u[k::-1]+u[k+1:]
  if sum(1<abs(v[i]-v[i+1])for i in r)<m:
   p=s(v,m-1)
   if p:return[k]+p
print s(a,5*n/3)

*(2 spaces = tab)

Try it online!

Saved 13 bytes borrowing a method for ranking a list.

DFS with a simple heuristic that checks whether a flip separates a pair of "pancakes" that would be adjacent when sorted. Sorts it in ascending order. Output is 0-indexed from the left where 0 flips the first 2 and so on. The number of moves used is (5/3)*n+1 < 5/3*(n+1) where (18/11)*n < (5/3)*n+1 < 5/3*(n+1) and (18/11)*n is a tighter upper bound found in 2009.