Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Insertion Sort with Recursion

MEDIUMProblemSolveExternal Links

Description

Given an array of integers, sort the array in ascending order using Recursive Insertion Sort.

In the standard (iterative) insertion sort, we use a loop to pick each element and insert it into its correct position among the already-sorted elements to its left. The recursive version replaces the outer loop with recursion:

  1. Base case: If the array has 1 or 0 elements, it is already sorted — return.
  2. Recursive step: Recursively sort the first n-1 elements. Then insert the nth element into its correct position in the sorted portion.

This problem helps you understand how iterative algorithms can be converted to recursive ones, deepening your understanding of recursion and how the call stack mirrors a loop.

Examples

Example 1

Input: arr = [12, 11, 13, 5, 6]

Output: [5, 6, 11, 12, 13]

Explanation: Recursive insertion sort is called with n=5. It first recursively sorts arr[0..3] = [12, 11, 13, 5] → [5, 11, 12, 13], then inserts arr[4]=6 into its correct position to produce [5, 6, 11, 12, 13].

Example 2

Input: arr = [3, 1, 2]

Output: [1, 2, 3]

Explanation: Recursively sort first 2 elements [3,1] → [1,3]. Then insert 2 into [1,3]: shift 3 right, place 2 at index 1. Result: [1, 2, 3].

Example 3

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

Output: [1, 2, 3, 4, 5]

Explanation: The array is already sorted. Each recursive call finds that the new element is already in the correct position (no shifting needed). This is the best-case scenario for insertion sort, requiring only O(n) comparisons.

Constraints

  • 1 ≤ arr.size() ≤ 10^3
  • 1 ≤ arr[i] ≤ 10^5

Editorial

Brute Force

Intuition

Before diving into the recursive version, let's first understand the iterative insertion sort — the standard approach that most beginners learn first.

Think of how you sort a hand of playing cards: you pick up cards one by one, and for each new card, you slide it into its correct position among the cards you already hold.

The algorithm maintains two regions in the array:

  • Sorted region (left side): starts with just the first element
  • Unsorted region (right side): everything else

In each pass, we take the first element from the unsorted region (the "key"), compare it with elements in the sorted region from right to left, shift larger elements one position to the right to make room, and insert the key at the correct position.

This is iterative — it uses a simple for loop for the outer pass and a while loop for the inner shifting.

Step-by-Step Explanation

Let's trace iterative insertion sort on arr = [12, 11, 13, 5, 6]:

Pass 1 (i=1, key=11): Sorted: [12]. Compare 11 with 12 → 11 < 12, shift 12 right. Insert 11 at index 0. Array: [11, 12, 13, 5, 6].

Pass 2 (i=2, key=13): Sorted: [11, 12]. Compare 13 with 12 → 13 > 12, stop. 13 is already in place. Array: [11, 12, 13, 5, 6].

Pass 3 (i=3, key=5): Sorted: [11, 12, 13]. Compare 5 with 13 → shift 13. Compare 5 with 12 → shift 12. Compare 5 with 11 → shift 11. Insert 5 at index 0. Array: [5, 11, 12, 13, 6].

Pass 4 (i=4, key=6): Sorted: [5, 11, 12, 13]. Compare 6 with 13 → shift 13. Compare 6 with 12 → shift 12. Compare 6 with 11 → shift 11. Compare 6 with 5 → 6 > 5, stop. Insert 6 at index 1. Array: [5, 6, 11, 12, 13].

Result: [5, 6, 11, 12, 13]

Iterative Insertion Sort — Key Insertion into Sorted Region — Watch how each element is picked as the 'key' and inserted into the correct position within the already-sorted left region by shifting larger elements to the right.

Algorithm

Iterative Insertion Sort:

  1. For i from 1 to n-1:
    a. Store key = arr[i]
    b. Set j = i - 1
    c. While j >= 0 and arr[j] > key:
    • Shift arr[j] to arr[j+1]
    • Decrement j
      d. Place key at arr[j+1]

Code

#include <vector>
using namespace std;

class Solution {
public:
    void insertionSort(vector<int>& arr) {
        int n = arr.size();
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            // Shift elements greater than key to the right
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
};
class Solution:
    def insertionSort(self, arr):
        n = len(arr)
        for i in range(1, n):
            key = arr[i]
            j = i - 1
            # Shift elements greater than key to the right
            while j >= 0 and arr[j] > key:
                arr[j + 1] = arr[j]
                j -= 1
            arr[j + 1] = key
class Solution {
    void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            // Shift elements greater than key to the right
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

Complexity Analysis

Time Complexity: O(n²)

  • Worst case (reverse sorted): Each element must be compared with all previous elements and shifted. Total comparisons: 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n²).
  • Best case (already sorted): Each element is compared once with its predecessor and no shifting occurs — O(n).
  • Average case: O(n²).

Space Complexity: O(1)

The iterative version uses only a constant amount of extra space (variables key, j).

Converting Iteration to Recursion

The iterative insertion sort uses a for loop that processes elements from index 1 to n-1. But what if we replace this loop with recursion?

The key observation is: the outer loop's behavior can be expressed recursively. Instead of a loop that says "sort elements 1 to n", recursion says:

  1. First, recursively sort the first n-1 elements
  2. Then, insert the nth element into its correct position

This is a natural recursive decomposition:

  • Subproblem: sort a smaller array (first n-1 elements)
  • Combine: insert one more element into the sorted result
  • Base case: n ≤ 1 means the array is trivially sorted

Notice that the inner while loop (the shifting/insertion step) stays the same — only the outer for loop becomes recursion. The recursion essentially "unrolls" the for loop into nested function calls on the call stack.

This conversion deepens understanding of how loops and recursion are fundamentally interchangeable. The call stack in recursion serves the same role as the loop counter in iteration.

Optimal Approach - Recursive Insertion Sort

Intuition

The recursive version mirrors the iterative logic exactly, but uses the call stack instead of a for loop:

Think of it like stacking plates: Before you can sort all 5 plates, you first need to sort 4 plates. Before sorting 4, sort 3. Before 3, sort 2. Before 2, sort 1 — and 1 plate is already sorted (base case!). Now work your way back: insert the 2nd plate correctly among 1 sorted plate, insert the 3rd among 2 sorted plates, and so on.

Each recursive call "defers" its work by saying: "I can't sort n elements until the first n-1 are sorted. Let me call myself on n-1 first, then I'll just handle the last element."

The call stack naturally handles the ordering — the deepest call (base case) returns first, then each call inserts its element in sequence, exactly like the for loop would.

Function structure:

recursiveInsertionSort(arr, n):
    if n <= 1: return          // Base case
    recursiveInsertionSort(arr, n-1)  // Sort first n-1
    // Insert arr[n-1] into sorted arr[0..n-2]
    key = arr[n-1]
    j = n - 2
    while j >= 0 and arr[j] > key:
        arr[j+1] = arr[j]
        j -= 1
    arr[j+1] = key

Step-by-Step Explanation

Let's trace the recursive calls on arr = [12, 11, 13, 5, 6]:

Call 1: sort(arr, 5) — n=5, need to sort first 4 elements first. Calls sort(arr, 4).

Call 2: sort(arr, 4) — n=4, need to sort first 3 elements first. Calls sort(arr, 3).

Call 3: sort(arr, 3) — n=3, need to sort first 2 elements first. Calls sort(arr, 2).

Call 4: sort(arr, 2) — n=2, need to sort first 1 element first. Calls sort(arr, 1).

Call 5: sort(arr, 1) — n=1, BASE CASE. Return immediately. Array unchanged: [12, 11, 13, 5, 6].

Return to Call 4 (n=2): Insert arr[1]=11 into sorted arr[0..0]=[12]. 11 < 12 → shift 12 right, insert 11. Array: [11, 12, 13, 5, 6].

Return to Call 3 (n=3): Insert arr[2]=13 into sorted arr[0..1]=[11,12]. 13 > 12 → already in place. Array: [11, 12, 13, 5, 6].

Return to Call 2 (n=4): Insert arr[3]=5 into sorted arr[0..2]=[11,12,13]. 5 < 13 → shift, 5 < 12 → shift, 5 < 11 → shift. Insert at 0. Array: [5, 11, 12, 13, 6].

Return to Call 1 (n=5): Insert arr[4]=6 into sorted arr[0..3]=[5,11,12,13]. 6 < 13 → shift, 6 < 12 → shift, 6 < 11 → shift, 6 > 5 → stop. Insert at 1. Array: [5, 6, 11, 12, 13].

Final Result: [5, 6, 11, 12, 13]

Recursive Insertion Sort — Call Stack Unwinding — Watch how recursion dives to the base case first (n=1), then as each call returns, it inserts one element into the sorted region — producing the same result as the iterative version.

Algorithm

recursiveInsertionSort(arr, n):

  1. Base case: if n <= 1, return (array of 0 or 1 elements is sorted)
  2. Recursive call: recursiveInsertionSort(arr, n - 1) — sort the first n-1 elements
  3. Insert step: Store key = arr[n - 1]
  4. Set j = n - 2
  5. While j >= 0 and arr[j] > key:
    • Shift: arr[j + 1] = arr[j]
    • Decrement: j -= 1
  6. Place key: arr[j + 1] = key

Code

#include <vector>
using namespace std;

class Solution {
public:
    void recursiveInsertionSort(vector<int>& arr, int n) {
        // Base case: single element is already sorted
        if (n <= 1) return;
        
        // Recursively sort first n-1 elements
        recursiveInsertionSort(arr, n - 1);
        
        // Insert the nth element into its correct position
        int key = arr[n - 1];
        int j = n - 2;
        
        // Shift elements greater than key to the right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
};
class Solution:
    def recursiveInsertionSort(self, arr, n):
        # Base case: single element is already sorted
        if n <= 1:
            return
        
        # Recursively sort first n-1 elements
        self.recursiveInsertionSort(arr, n - 1)
        
        # Insert the nth element into its correct position
        key = arr[n - 1]
        j = n - 2
        
        # Shift elements greater than key to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
class Solution {
    void recursiveInsertionSort(int[] arr, int n) {
        // Base case: single element is already sorted
        if (n <= 1) return;
        
        // Recursively sort first n-1 elements
        recursiveInsertionSort(arr, n - 1);
        
        // Insert the nth element into its correct position
        int key = arr[n - 1];
        int j = n - 2;
        
        // Shift elements greater than key to the right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The time complexity is identical to the iterative version. The recursive version makes n-1 recursive calls, and at each call level, the insertion step takes up to O(k) time where k is the current subarray size. Total work: 1 + 2 + ... + (n-1) = O(n²) in the worst case.

  • Worst case (reverse sorted): O(n²) — each insertion shifts all previous elements
  • Best case (already sorted): O(n) — each insertion finds the element already in place
  • Average case: O(n²)

Space Complexity: O(n)

Unlike the iterative version which uses O(1) space, the recursive version uses O(n) space due to the recursion call stack. Each of the n recursive calls adds a frame to the stack. This is the key trade-off when converting iteration to recursion — we trade constant space for call-stack space.

For very large arrays (n close to 10^5), this could cause a stack overflow. This is why the iterative version is generally preferred in production code, while the recursive version is valuable for learning recursion concepts.