In Insertion sort, we use the compare$-$and$-$swap operation to do sorting. In this question, we shall use

a more general operation flip to do sorting.

Let $L$:$a_1,a_2,$dots,$a_n$ be a list of elements $($drawn from a totally ordered set$).$ The flip operation

flip$(L,i,j)$ converts the list $a_1,a_2,$dots,$a_{i-1},a_i,a_{i+1},$dots,$a_{j-1},a_j,a_{j+1},$dots,$a_n$

$to{a}_1,a_2,$dots,$a_{i-1},a_j,a_{j-1},$dots,$a_{i+1},a_i,a_{j+1},$dots,$a_n$

i$.$e$.$ filp$(L,i,j)$ reverses the order of elements in the sublist $a_i,a_{i+1},$dots,$a_{j-1},a_j.$

Assuming flip $(L,i,j)$ takes $O(j-i)$ time.

$($a$)$ Given a list of elements $a_1,a_2,$dots,$a_n$ such that $a_{i}in\{0,1\},1in.$ Present an algorithm that

sorts the list in $O(nlgn)$ time. You are allowed to use only the flip operation to rearrange the

elements.

$($b$)$ Using the algorithm of Part $($a$)$ as a subroutine, present an $O(n^{2}lgn)-$time algorithm that

sorts a list of $n$ elements, $a_i,1in,$ drawn from a totally ordered set.

$($Note: You are to reduce sorting to the problem of sorting a list of $0\text{'}$s and $1\text{'}$s$.$ Hence,

presenting an algorithm without using Part $($a$)$ will receive a $0$ mark.$)$