2.2 Insertion Sort and Binary Search (25 pts) In the class we saw that if we only care about comparisons we can modify Insertion Sort to make sure it performs O(nlogn) comparisons on every input. The idea is to use binary search inside the for loop to find the right position of element i. The modified pseudo code is below Input: An array A-Ia 1,a 2, . .. ,a n] of n elements Output: The array A in sorted order for i-2 to n 1. Use Binary search on A[1 i-1] to find the largest index j such that A[j]