Assume that our input array A contains both numbers and letters. We will analyze a variant of insertion sort (SplitInsertionSort) that outputs two lists: one with only numbers and another with only letters. Naturally, each list will be sorted.

(a) Write pseudocode for SplitInsertionSort

(b) Write a recurrence equation for this algorithm

(c) Use the recurrence equation above to prove the worst-case running time of this algorithm