## 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
insertion-sort(arr, 0)
insert 5
return arr = [5]
insertion-sort(arr, 1)
insert 2
return arr = [5, 2]
insertion-sort(arr, 2)
insert 9
return arr = [2, 5, 9]
insertion-sort(arr, 3)
insert 7
return arr = [2, 5, 7, 9]
insertion-sort(arr, 4)
insert 14
return arr = [2, 5, 7, 9, 14]
insertion-sort(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 n-1 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 n-1 elements
recursive_insertion_sort( arr, n-1 )
int val = arr[n-1]
int pos = n-2
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`

with`n-2`

? - In the last line of pseudo-code, how did we make sure that
`pos+1`

is the correct position for the`val`

to be inserted such that the`array[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!**