Searching, Sorting, Performance and Efficiency (Weeks 11, 13 and 14) - 50 points Problem 3.1 (4 points): Which of the following sort algorithms has the lowest worst-case complexity for an array that is already in sorted order? a) Selection sort b) Insertion sort c) Merge sort Problem 3.2 (4 points): Which sorting algorithm will take the least amount of time when all elements of the input array are identical? a) Selections sort b) Insertion Sort c) Merge Sort Problem 3.3 (5 points): Suppose an array, arr contains 2nintegers,whereeach consecutive pair of values in arr is in reverse order and both values in the pair are greater than the values in all pairs to the left as shown in the examples in the table below. The insertion sort algorithm is performed to sort such arrays. What is the worst-case time omplexity of the insertion sort on arrays that contain data that is in the order described above? a. O(n2) b. O(nlogn) c. O(logn) d. O(n)