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/.