[Solved]: Expected number of random interval flips needed for sorting a random array

$Omega(n!)$ is an easy lower bound: your algorithm certainly needs at least $Omega(n!)$ iterations on average. Obviously, you need to try at least $Theta(n!)$ different permutations of the array before you have a decent chance of getting the elements into sorted order (since you started with a uniformly random permutation). Also, one can show that $O(n! cdot n lg n)$ is an upper bound on the number of iterations needed. Here’s why. It’s known that there is a constant $c$ such that composing $k=c n lg n + o(n lg n)$ randomly chosen transpositions gives you something that is close to a random permutation. So, look only at every $k$th iteration of your algorithm, and consider the permutation generated at each such time instant. Each one is approximately a random permutation (independent of all others). After checking $Theta(n!)$ independent random permutations, with good probability at least one of them will put the array into sorted order. Therefore, your algorithm needs at most $O(n! cdot k) = O(n! cdot n lg n)$ iterations. Or, to put it another way, if we tested for sortedness only at every $k$th iteration of your algorithm, the result would be essentially equivalent to Bogosort, so your algorithm performs at most $k$ times as many iterations as Bogosort — thus your algorithm needs at most $O(n! cdot k) = O(n! cdot n lg n)$ iterations. So we know that the answer is at least $Omega(n!)$ and at most $O(n! cdot n lg n)$. Those two answers are very close (they differ only by a factor that is logarithmic in the number of iterations), so this doesn’t leave much of a gap — it almost totally resolves the question. If you wanted a more precise answer, probably a more delicate analysis would be needed to eliminate the gap — but lacking clear motivation for studying this problem, it’s not clear it’s worthwhile to spend that level of energy on it. How do we know that composing $O(n lg n)$ random transpositions gives you something close to a random permutation? That was proven in the following paper: Generating a Random Permutation with Random Transpositions. Persi Diaconis, Mehrdad Shahshahani. 1981. See also https://paulrs.wordpress.com/2014/07/22/generating-a-random-permutation/.