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:
1 2 3 if n > 1 RECURSE-INSERTION-SORT(A, n - 1) INSERT(A, n)
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 ,