Recursive Insertion Sort

1/2/25, 12:15 PM Recursive Insertion Sort
AfterAcademy
Admin AfterAcademy
23 Sep 2020
Recursive Insertion Sort
Difficulty: Medium
Understanding The Problem

Problem Description
Write a program for the recursive implementation of Insertion Sort.
Example 1
https://afteracademy.com/blog/recursive-insertion-sort/ 1/7
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]
insert 2
return arr = [5, 2]
insert 9
return arr = [2, 5, 9]
insert 7
return arr = [2, 5, 7, 9]
insert 14
return arr = [2, 5, 7, 9, 14]
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!
Recommended for You
Letter Combinations of a Reverse a Stack Using

Phone Number Recursion
Given a string str, containing digits from 2 - Given a stack of integers st, write a program
9 inclusive, write a program to return all the to reverse the stack using recursion. This
possible letter combinations that the problem will clear the concept of recursion.
number could represent. This is a popular
coding interview question based on
backtracking and recursive approach.
Admin AfterAcademy Admin AfterAcademy

12 Oct 2020 6 Oct 2020
Sort List - Merge Sort Wave Array

Sort a linked list using Merge Sort. This is a You are given an unsorted array of
very famous interview problem that integers(arr) of length n, write a program to
demonstrates the concept of recursion. This sort it in wave form. The array elements in
problem is quite similar to Merge Sort in the resultant array must be such that arr[0]
Arrays. >= arr[1] <= arr[2] >= arr[3] <= arr[4] ... and so
on. If there are multiple sorted orders in
wave-form, return the one which is
lexicographically smallest.

12 Sep 2020 20 Aug 2020
Merge Two Sorted Arrays Quick Sort

You are given two sorted arrays arr1[ ] and Sorting is a process of arranging items
arr2[ ] of sizes m and n respectively. Write a systematically. There are several ways to
program to merge them in such a way that sort a list of items. A very useful sorting
the resultant array is sorted too. algorithm in all of the sorting algorithms is
quicksort. Given an array of integers arr[],
write a program to sort the array in
ascending order using Quick Sort.

17 Aug 2020 10 Aug 2020
Connect With Your Mentors
Janishar Ali Amit Shekhar

Founder | IIT-BHU | 10 Yrs Exp. Founder | IIT-BHU | 10 Yrs Exp.
Copyright 2022, MindOrks Nextgen Private Limited

Recursive Insertion Sort

Uploaded by

Copyright:

Available Formats

Recursive Insertion Sort

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Recursive Insertion Sort

Uploaded by

Copyright:

Available Formats

1/2/25, 12:15 PM Recursive Insertion Sort

Recursive Insertion Sort

Understanding The Problem

Write a program for the recursive implementation of Insertion Sort.

Input: arr[] = [5, 2, 3, 1]

Input: arr[] = [5, 1, 1, 2, 0, 0]

An insertion sort works like this

sorted and we can simply return from there.

arr = [ 5, 2, 9, 7, 14, 8], size = 6

You can try this problem here.

Base Case: If array size is 1 or smaller, return.

Recursively sort first n-1 elements.

void recursive_insertion_sort(int arr[], int n) {

Time Complexity: O(n²)

Space Complexity: O(n) (How?)

Critical Ideas To Think

Why did we initialize pos with n-2 ?

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 Bubble Sort

The factorial of a number using Recursion

Happy Coding, Enjoy Algorithms!

Recommended for You

Letter Combinations of a Reverse a Stack Using

Admin AfterAcademy Admin AfterAcademy

Sort List - Merge Sort Wave Array

Admin AfterAcademy Admin AfterAcademy

Merge Two Sorted Arrays Quick Sort

Admin AfterAcademy Admin AfterAcademy

Connect With Your Mentors

Janishar Ali Amit Shekhar

Copyright 2022, MindOrks Nextgen Private Limited

You might also like