ā Question
You can also think of insertion sort as a recursive algorithm. In order to sort $A[1:n]$, recursively sort the subarray $A[1:n-1]$ and then insert $A[n]$ into the sorted subarray $A[1:n-1]$. Write the pseudocode for this recursive version of insertion sort. Give a recurrence for its worst-case running time.