We say that an array A is c$-$nice for a constant c if for all $1<=$ i $<$ j $<=$ n such that j $$ i $>=$ c$,$ we have that A$[$i$]<=$ A$[$j$].$ For example, a $1-$nice array is completely sorted $($in ascending order$).$ In this problem we will sort such c$-$nice arrays A using various sorting algorithms and compare the results. $($You may assume that A has n distinct elements.$)$

$($a$)$ For an element at position i in the array, what is the best lower bound you can give on its rank? What is the best upper bound?

$($b$)$In asymptotic notation $($remember that c is a constant$)$ what is the worst$-$case running time of InsertionSort on a c$-$nice array? $$

Now consider a run of Quicksort on a c$-$nice array, where the pivot element is chosen deterministically as the last element of the array.

$($c$)$ Argue that after partitioning, the two subarrays A$[1...$ q $1]$ and A$[$q $+1...$ n$]$ to the left and to the right of the pivot, respectively, are both c$-$nice.

d$)$From the lecture you already know that the running time of quicksort on sorted arrays is $\backslash$Theta $($n$^2).$ Let B$($n$)$ denote the best$-$case running time of Quicksort on c$-$nice array with n elements. Using your results from $($a$)$ and $($c$),$ derive a recurrence for B$($n$)$ and solve it$.$

$($e$)$Asymptotically$,$ which is faster on c$-$nice arrays: the worst$-$case running time of insertion sort or the best$-$case running time of quicksort? $$

$($f$)$Now use min$-$heaps $($in a slightly clever way$)$ to get an algorithm with the following specification. It takes as input an array A and a integer value b in $\{1,...,$ n$\},$ and always runs in time O$($n log b$)$ time. The output is always a permutation of the elements of A$.$ However, if the input A is c$-$nice for some c $<=$ b$,$ the output is the sorted version of A$.$

$($g$)$ When you are sorting arrays, you will not know what c is$.$ Here$$s a general $$guessing$$ strategy: $$

$1.$ Nice$-$But$-$Weird$-$Sort$($A$)$

$2.$ let i $0$

$3.$ let b$2^$i

$4.$ B $$ Sort$-$Nice$($A$,$ b$)$

$5.$ if B is not sorted, set i $$ i $+1,$ goto line $2.$

Suppose the array is c$^-$nice. Give the best runtime bound you can give for this algorithm in terms of n and log c$^.$

$($h$)$ Change your choice for b to ensure that the algorithm above runs in time O$($n log c$^).$