Recursive Insertion Sort in Python

You’re asked to sort an array using Insertion Sort, but instead of the classic iterative two-loop approach, you must implement it recursively in Python.

Here’s the [Problem Link] to begin with.

Insertion Sort works by building the sorted portion of the array one element at a time: each new key is inserted into its correct place among the already-sorted elements to its left.

Example

The recursive version mimics the “expand-then-insert” logic by sorting the first n – 1 elements recursively, then inserting the n-th element (key) into that sorted prefix.

Recursive Insertion Sort Solution

Intuition & Approach

1. Base Case – A segment of length 0 or 1 is inherently sorted; stop recursion.
2. Recursive Step – Recursively sort the prefix arr[0 … n – 2].
3. Insertion Phase – Treat arr[n – 1] as key; shift larger elements in the sorted prefix one position to the right until you find the correct spot, then insert key.
4. The recursion depth decreases by one each call, ultimately reaching the base case.

Code Implementation

class Solution:
    def func(self, arr, n):
        # Base case: array of size 0 or 1 is already sorted
        if n <= 1:
            return
        
        # Recursively sort the first n-1 elements
        self.func(arr, n - 1)

        # Insert arr[n-1] (the 'key') into the sorted prefix
        key = arr[n - 1]      # element to place
        j = n - 2             # start from the last index of the sorted prefix
        
        # Shift elements that are greater than 'key' to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        # Position found; insert the key
        arr[j + 1] = key

    def insertionSort(self, arr):
        # function that kicks off recursion for the whole array
        self.func(arr, len(arr))

Code Explanation

• self.func(arr, n – 1) sorts the prefix by recursion before any insertion takes place.
• while j >= 0 and arr[j] > key walks backward through the sorted prefix, shifting larger elements rightward to make space.
• arr[j + 1] = key drops key into its rightful place, leaving arr[0 … n – 1] fully sorted when the function returns.

Dry Run (Array [4, 3, 2])

Unwinding reconstructs the fully sorted array [2, 3, 4].

Time & Space Complexity

• Time: O(n²) – identical to iterative Insertion Sort, because each insertion can shift up to n elements in the worst case.
• Space: O(n) – recursion adds a stack frame per level (Python doesn’t optimize tail calls).

Conclusion

Recursive Insertion Sort keeps the simplicity of its iterative counterpart while showcasing how “process-a-prefix → insert-last” can replace an outer loop. Though its quadratic time makes it unsuitable for very large inputs, it remains a valuable technique for learning recursion, algorithm design, and problem decomposition.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.