Problem $4.$ In this problem, we consider a non$-$standard sorting algorithm called the emphSlow Sort.

Given an array A$[1$ : n$]$ of n integers, the algorithm is as follows: $$ Slow$-$Sort$($A$[1$ : n$])$:

$1.$ If n $<100,$ run merge sort $($or selection sort or insertion sort$)$ on A$.$

$2.$ Otherwise, run Slow$-$Sort$($A$[1$ : n $1]),$ Slow$-$Sort $($A$[2$ : n$]),$ and Slow$-$Sort$($A$[1$ : n $1])$ again.

We now analyze this algorithm.

$($a$)$ Prove the correctness of Slow$-$Sort