Reverse: If some segment of permutation of length K is in sorted order, we can reverse it in \lfloor \frac{K}{2} \rfloor operations.
How: If this segment is [L:R], just apply the operation for [L, R], [L+1, R-1], \ldots, [L+\lfloor \frac{K}{2} \rfloor-1, R-\lfloor \frac{K}{2} \rfloor+1] in this order.
Merge: Suppose that we have two consecutive sorted segments: P[L:M-1] and P[M:R]. Let’s show how to ``merge’’ them: to sort the entire segment [L:R].
How: If P_{M-1} < P_M, the entire segment is already sorted. Otherwise, consider the largest 1 \le z \le min(M-L, R-M+1), such that P_{M-z}>P_{M+z-1}. Then, reverse segments P[M-z:M-1] and P[M:M+z-1], and reverse the entire P[M-z:M+z-1], as it’s sorted (just in decreasing order). Now, all elements are in the “right” parts among [L:M-1], [M:R], and we just have to sort both of them. Note that each of them is two consecutive sorted segments! So, we just have to “Merge” segments [L:M-z-1], [M-z:M-1] and [M:M+z-1], [M+z, R].
Sort: Suppose that we want to sort the entire segment [L: R].
How: If L=R, no operations are needed. Otherwise, let M = \lceil \frac{L+R}{2} \rceil. Sort [L:M-1] and [M:R] recursively, and then merge these segments.
Why does this work in not too many operations?
Suppose that we are merging segments of lengths x and y with 1\le x \le y (y<x is the same). We can prove by induction that this entire merge will take at most (x+y)(\log_2{x}+1) operations (it’s left as an exercise for the reader).
Now we can estimate the number of operations needed to sort a segment of length K. We have recurrence T(K) = 2T(\frac{K}{2}) + K\log_2{K}, which results in T(K) \le roughly \frac{K\log_2{K}^2}{2}. For K = 30000, this is around 3.32 millions, so 4 millions are enough. In fact, we weren’t able to construct a test where we need more than 2M operations.