We can express Insertion Sort for sorting an array A[1..n] recursively as follows: if A has one element, it is sorted; otherwise recursively sort A[1..n1] and then insert A[n] into the sorted array A[1..n1]. First give the algotithm in pseudo code, then derive the recurrence relation expressing the run time T(n) of the algorithm. Show your work. Do not forget the base case. You do not have to solve the recurrence.