Problem statement
Given a 1-indexed array of 0s and 1s of length $$$n$$$, sort it in $$$O(n)$$$ time with a model of computation that allows only read on the array and reversal operations for write.
A reversal operation is done by choosing a subarray with bounds $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le n$$$, and reversing it. A reversal operation takes $$$O(r-l)$$$ time.
Note — The goal is not to achieve $$$O(n)$$$ number of reversals, but total $$$O(n)$$$ time.
Note — We cannot optimize the reversal operation. The model of computation does not allow that. Any reversal on a subarray of size $$$S$$$ will take $$$O(S)$$$. You can think of it in a way that a stupid monkey is doing the reversals, and he will always take $$$O(S)$$$ time for a subarray of size $$$S$$$. You can only tell him $$$l$$$ and $$$r$$$, not how to do the reversal
Where am I on this?
A merge-sort based solution is straightforward, but $$$O(n*logn)$$$
I think it is impossible to solve it in O(n)
I tried to consider an array of repeating $$$0 1$$$, and never found a way to sort it in $$$O(n)$$$
