In the lecture you learned about the InsertionSort algorithm. which runs through the elements of a

list from left to right and sorts them in ascending order. The aim of this task is to deepen your

understanding of the algorithm and to develop a mirrored variation of the algorithm.

$($a$)$ Rewrite InsertionSort so that the resulting algorithm traverses the elements from right to left

and sorts them in ascending order and justify your design. The insertion should be mirrored to the

original algorithm, i$.$e$.$ on the right side of the array. The algorithm should continue to be

implemented iteratively, i$.$e$.$ via an outer and an inner loop.

$($b$)$ Using the algorithm in $H1(a),$ sort the following array of strings alphabetically:

Before each run of the outer loop, specify the state of the $($partially sorted$)$ array and mark

the element currently being viewed. Also consider the execution of the loop, which is aborted

due to the loop condition.

$($c$)$ Prove the correctness of your algorithm from $H1($a$).$

$($d$)$ In the divide and conquer approach, a problem is divided $($recursively$)$ into smaller sub$-$problems that are

easier to solve, and then the solutions of these sub$-$problems are merged to solve the overall

problem. The aim of this sub$-$task is to create initial points of contact with this approach. To do this, design

the algorithm from $H1(a)$ as a recursive method RecursivelnsertionSort$($A$,$