We are given an array $A$ of $n$ positive and $n$ negative numbers, which are intermixed. We would

like to rearrange the numbers in A such that positive and negative numbers appear in alternating

order.

For example, if $n=4$ and then

or are both correct solutions. Describe a linear$-$time $((n))$ in$-$

place algorithm to solve this problem $($an in$-$place algorithm produces the solution within the input

array, using at most $(1)$ extra space$).$

Prove the correctness of your algorithm using loop invariants and analyze its runtime and space

requirement.