Recursive Insertion Sort
Difficulty: Medium
Understanding The Problem
Problem Description
Write a program for the recursive implementation of Insertion Sort.
Example 1
Input: arr[] = [5, 2, 3, 1]
Output: [1, 2, 3, 5]
Explanation: The output is the sorted array.
Example 2
Input: arr[] = [5, 1, 1, 2, 0, 0]
Output: [0, 0, 1, 1, 2, 5]
Explanation: The output is the sorted array.
An insertion sort works like this
Solution
The problem expects us to sort an array using Insertion sort and we have to do it recursively. You can read about insertion sort here.
Now, we know that Recursion is made for solving problems that can be broken down into smaller, repetitive problems. In this case, we can define our smaller problems in this way “we have a sorted array and now we have to insert a number in that sorted array”.
Now, every recursive function requires a base case for its termination. In this case, we can say that if the array is of size 1, then the array is already sorted and we can simply return from there.
Now, the problem is to find a way to insert a value in a sorted array and that can be done as shown in the above visualization. We will simply shift the array elements to find the right position for the new element. As soon as we place the new element in its correct position, our sorted array size will increase by one.
Example:
arr = [ 5, 2, 9, 7, 14, 8], size = 6
insertionsort(arr, 0)
insert 5
return arr = [5]
insertionsort(arr, 1)
insert 2
return arr = [5, 2]
insertionsort(arr, 2)
insert 9
return arr = [2, 5, 9]
insertionsort(arr, 3)
insert 7
return arr = [2, 5, 7, 9]
insertionsort(arr, 4)
insert 14
return arr = [2, 5, 7, 9, 14]
insertionsort(arr, 5)
insert 8
return arr = [2, 5, 7, 8, 9, 14]
You can try this problem here.
Solution Steps
 Base Case: If array size is 1 or smaller, return.
 Recursively sort first n1 elements.
 Insert the last element at its correct position in the sorted array.
Pseudo Code
void recursive_insertion_sort(int arr[], int n) {
// Base case
if (n <= 1)
return
// Sort first n1 elements
recursive_insertion_sort( arr, n1 )
int val = arr[n1]
int pos = n2
while (pos >= 0 && arr[pos] > val) {
arr[pos+1] = arr[pos]
pos = pos  1
}
arr[pos+1] = val
}
Complexity Analysis
Time Complexity: O(n²)
Space Complexity: O(n) (How?)
Critical Ideas To Think
 Can you prove that our assumption about the array is sorted in each recursion frame is correct for every case?

Why did we initialize
pos
withn2
? 
In the last line of pseudocode, how did we make sure that
pos+1
is the correct position for theval
to be inserted such that thearray[0..n]
will stay sorted?  Can you draw the recursion tree for this sorting?
 Is this solution intuitive to you?
 How this approach is different from the iteration?
Suggested Problems To Solve
 Recursive Selection Sort
 Recursive Bubble Sort
 Merge Sort
 The factorial of a number using Recursion
Please comment down below if you find an error/bug in the above explanation.
Happy Coding, Enjoy Algorithms!