0
(See the previous iteration.)
Now I have optimized my natural merge sort: Suppose the input sequence is
$$\langle 2, 1, 4, 3, 6, 5, \dots, n, n - 1 \rangle.$$
My previous iterations would degrade to \$\Theta(n \log n)\$ on this input. This version will not: After reversing the second run (\$\l...