$(12)$ Describe the running time of each of the following algorithms

for sorting an array of length $n$ into increasing order if the input

array is already in increasing order $($for example, $1,2,3,$dots,$n).$

a$)$ Merge sort. $(nlgn).$

b$)$ Insertion sort. $(n).$

c$)$ Heap sort. $(nlgn).$

d$)$ Quicksort $($assume that the pivot element is the rightmost

element$).(n^2).$