4. Suppose we sort an array of numbers, but it turns out every element of the array is the same, e.g., {17, 17, 17, ..., 17}. (So, in hindsight, the sorting is useless.)

a) What is the asymptotic running time of insertion sort in this case?

b) What is the asymptotic running time of selection sort in this case?

c) What is the asymptotic running time of merge sort in this case?

d) What is the asymptotic running time of quick sort in this case?

e) Give an example input list for which merge-sort and heap-sort take O(n log n) time, but for which insertion sort takes O(n) time. What if the list is reversed?

Please give some explination as to why, but it dosen't need to be an essay.