Problem 3. (a) Recall the insertion-sort-like algorithm in Problem 4 from Homework 2, where you know that certain pairs of contiguous items in the sorted order are contiguous in the input. Write the pseudo-code for this algorithm, where the outer loop is done by recursion. Assume that n is even. (b) Write a recurrence for the number of comparisons in the worst case (assuming that n is even)