We can modify Insertion Sort to insert a pair of elements at a time, instead of only one element: Find the larger element of the pair and put it into its proper location in the sorted array using linear search (as in standard insertion sort). Then, starting from where the larger element ended up, put the smaller element into its proper location again using linear search. (a) Write the pseudo code, using a sentinel, for this algorithm. You may assume that the size of the array is even. (b) Assume the size of the array n = 4. i. What is the best-case number of comparisons? Just state the number and show your input. Otherwise, no justification needed. ii. What is the worst-case number of comparisons? Just state the number and show your input. Otherwise, no justification needed. iii. What is the average-case number of comparisons? Justify. HINT: There are 24 pos- sible orderings, which is a lot. The calculation is more manageable if you realize that the first pair of elements essentially defines the whole ordering. (c) Calculate the average case number of comparisons for general n, where n is even. Show your work. (d) How does the average case number of comparisons compare with the average case of standard insertion sort?