Insertion sort can be expressed as a recursive procedure as follows. In order to sort , we recursively sort and then insert A[n] into the sorted array . Write a recurrence for the running time of this recursive version of insertion sort.

There are two steps in this recursive sorting algorithm:

- Sort the sub-array
- Insert into the sorted sub-array from step 1 in proper position

For , step 1 doesn’t take any time as the sub-array is an empty array and step 2 takes constant time, i.e. the algorithm runs in time.

For , step 1 again calls for the recursion for and step 2 runs in time.

So, we can write the recurrence as:

### Additional Analysis

**Pseudo-code #1:** `RECURSE-INSERTION-SORT(A, n)`

1
2
3

if n > 1
RECURSE-INSERTION-SORT(A, n - 1)
INSERT(A, n)

**Pseudo-code #2:** `INSERT(A, k)`

1
2
3
4
5
6

key = A[k]
index = k - 1
while index > 0 and A[index] > key
A[index + 1] = A[index]
index = index - 1
A[index + 1] = key

**Solution to the Recurrence:** Let us assume that for , , where is some constant. And on average for , inserting an element in its proper position in a sorted array requires shifting half of the elements, i.e. time ( for shifting the elements and for inserting the element).

So, we can rewrite the recurrence as:

So for any general ,