### 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)$↵
↵
<spoiler summary="My hand wavy proof for this">↵
↵
Assume for the sake of contradiction that there exists an algorithm that can solve the problem for every array of size $n$ in $n*C$ steps. Where $C$ is a constant.↵
↵
Consider this array of repeating $0 1$ of even size $n$. Example: $0 1 0 1 0 1 0 1 0 1$↵
↵
Split it to two parts↵
```↵
0 1 .... 0 1 0 1 0 1 | 0 1 0 1 0 .... 0 1↵
```↵
↵
Now the 1s in the left are to be moved to the right, and 1s in the right should not go to the left.↵
↵
This part is hard to prove (I will attempt to get a more sophisticated and clearer arguements), but to solve it optimally, you must first sort both halves and get the array to this state↵
↵
```↵
0 0 0 ... 1 1 1 | 0 0 0 .... 1 1 1↵
```↵
If you dont get it this way, any reversal operation you do will with a subarray will take unwanted elements with it... ↵
↵
↵
So you must take $O(n/2 * C)$ + $O(n/2 * C)$ steps to reach here, and then $O(n/2)$ steps to do another reversal↵
Making total steps $O(n*(C + 0.5))$↵
↵
↵
</spoiler>↵
↵
### Help needed↵
↵
If there is a way, please explain.↵
↵
If not, any other intuitions to prove that it's not possible?↵
↵
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)$↵
↵
<spoiler summary="My hand wavy proof for this">↵
↵
Assume for the sake of contradiction that there exists an algorithm that can solve the problem for every array of size $n$ in $n*C$ steps. Where $C$ is a constant.↵
↵
Consider this array of repeating $0 1$ of even size $n$. Example: $0 1 0 1 0 1 0 1 0 1$↵
↵
Split it to two parts↵
```↵
0 1 .... 0 1 0 1 0 1 | 0 1 0 1 0 .... 0 1↵
```↵
↵
Now the 1s in the left are to be moved to the right, and 1s in the right should not go to the left.↵
↵
This part is hard to prove (I will attempt to get a more sophisticated and clearer arguements), but to solve it optimally, you must first sort both halves and get the array to this state↵
↵
```↵
0 0 0 ... 1 1 1 | 0 0 0 .... 1 1 1↵
```↵
If you dont get it this way, any reversal operation you do will with a subarray will take unwanted elements with it... ↵
↵
↵
So you must take $O(n/2 * C)$ + $O(n/2 * C)$ steps to reach here, and then $O(n/2)$ steps to do another reversal↵
Making total steps $O(n*(C + 0.5))$↵
↵
↵
</spoiler>↵
↵
### Help needed↵
↵
If there is a way, please explain.↵
↵
If not, any other intuitions to prove that it's not possible?↵
↵
