$5$ Sorting $[15$ points$]$

Consider array $\backslash ($ A$=[3,8,5,9,2,7,6,4]\backslash )$ which has size $8.$

$($i$)(3$ points$)$ To sort the array $\backslash ($ A $\backslash )$ by the call MergeSort $\backslash (($A$,1,8)\backslash ),$ how many recursive calls to MergeSort are made? Show the first four such calls.

$($ii$)(4$ points$)$ Show the resulting array by the call Build$-$Max$-$Heap$($A$),$ with the original array $\backslash ($ A $\backslash )$ above.

$($iii$)(4$ points$)$ Show the resulting array by the call $\backslash (\backslash$operatorname$\{$Partition$\}($A$,1,8)\backslash ),$ with the original array $\backslash ($ A $\backslash ).$

$($iv$)(4$ points$)$ Consider the four sorting algorithms that we have studied: InsertionSort, MergeSort, HeapSort, and QuickSort. Suppose the input arrays satisfy the following condition: Each element of the given array of size $\backslash ($ n $\backslash )$ may be out of position at most by one. That is$,$ if an element at index $\backslash ($ i $\backslash )$ in the sorted array, its index in the given array can be $\backslash ($ i$-1,$ i $\backslash )$ or $\backslash ($ i$+1\backslash )($of course, as special cases, if $\backslash ($ i$=1\backslash )$ or $\backslash ($ i$=$n $\backslash ),$ its index in the given array can only be one of the two that are available$).$ For example, an element at index $5$ in the sorted array can be at indexes $4,5,$ or $6$ in the given array. For these types of input arrays, which sorting algorithm is the most efficient, and why?