$4$ Flipping frogs

You have encountered a troupe of n frogs who are each labeled with a number $0,...,$ n $1,$

where n is a power of $2.$

The n frogs dance in a line, and they only know one type of dance move, called Flip$($i$,$j$)$:

for any i and j so that $0<=$ i $<$ j $<=$ n$,$ Flip$($i$,$j$)$ flips the order of the frogs standing in

positions i $,$ i $+1,...,$ j $1.$ For example, if the frogs started out like this:

$01234567$

then after executing Flip$(1,5),$ the frogs would look like this:

$04321567$

Executing this dance move is pretty complicated: it takes the frogs O$(|$i $$ j$|)$ seconds to

implement Flip$($i$,$j$).$

In this problem, you will design and analyze an algorithm to sort the n frogs by their labels,

which uses Flip, the only move the frogs know. However, you don$$t know the original order

of the frogs until you see them, and so you may also need to spend some extra time in

between the Flip operations computing which indices i and j you want to call Flip on$.$

Below, you will consider algorithms which take as input an array that contains the frog$$s

initial positions $($for example, if the frogs were originally organized as the picture above $($after

the flip$),$ then the input array would be A $=[0,4,3,2,1,5,6,7]).$ In addition to normal

computation, which can be used to compute indices i and j$,$ your algorithm is allowed to call

Flip$($i$,$j$),$ which will cause the frogs to implement the Flip$($i$,$j$)$ dance. The algorithm

will wait until the frogs are done executing that dance move to continue its computations.

Thus, the total running time of the algorithm includes both the time spent computing, and

the time that the frogs spend dancing.

$4\mathrm{.}1$ Partitioning the frogs $(15$ pt$.)$

First, you will design an algorithm that tells the frogs how to perform a dance called Partition$($i$).$

For this dance, the frogs will partition themselves around the frog in position i $,$ so that all of

the frogs whose labels are smaller than that frog$$s label will end up to the left, and all the

frogs whose labels are larger will end up to the right. For example, if the situation were this:

$04321765$

then after executing Partition$(3),$ the frogs partition themselves around the frog in position

$3,$ whose label is $2.$ The resulting frogs formation could look like this:

$7$