Topics › Sorting › Sorting-II

Recursive Insertion Sort

Easy TUF ID 882 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an array arr of n integers. Sort it in non-decreasing order using insertion sort, but implement the algorithm recursively: the outer loop that walks through the elements must be replaced by a recursive call. The inner insertion may stay a loop or be made recursive too.

Constraints: 1 ≤ n ≤ 10^3, values fit in a 32-bit signed integer. Duplicates and negative numbers are allowed.

Example 1

arr = [14, 9, 15, 12, 6, 8, 13]
answer = [6, 8, 9, 12, 13, 14, 15]    // every element is <= the one after it

Example 2

arr = [5, 4, 4, 1, 1]
answer = [1, 1, 4, 4, 5]              // duplicates stay together

Approach 1: Recurse forward over the array

Intuition. Iterative insertion sort maintains the invariant arr[0..i-1] is sorted and, for i = 1, 2, ..., n - 1, inserts arr[i] into that prefix by swapping it leftwards past every larger element. The outer loop only advances i.

Turn i into a parameter. A call f(i) assumes the prefix before i is sorted, inserts arr[i], and then calls f(i + 1). The base case is i >= n: every element has been inserted. Starting the recursion at i = 0 is harmless (the insertion loop does nothing for the first element) and matches the A2Z sheet’s formulation; starting at 1 would work equally well.

Algorithm.

1. recursiveInsertionSort(arr) starts the recursion with i = 0.
2. recursiveInsertionSort(arr, i): if i >= n return.
3. Set j = i; while j > 0 and arr[j - 1] > arr[j], swap them and j--.
4. Call recursiveInsertionSort(arr, i + 1).

static void recursiveInsertionSort(int[] arr) {
    recursiveInsertionSort(arr, 0);
}

static void recursiveInsertionSort(int[] arr, int i) {
    if (i >= arr.length) return;
    int j = i;
    while (j > 0 && arr[j - 1] > arr[j]) {
        int tmp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = tmp;
        j--;
    }
    recursiveInsertionSort(arr, i + 1);
}

Dry run on arr = [14, 9, 15, 12, 6, 8, 13]:

The sorted prefix grows by one element per call; the untouched suffix shrinks until it is empty.

Complexity. Time O(n^2) worst case (reversed input: call f(i) makes i swaps, n(n-1)/2 in total) and O(n) best case (sorted input: one comparison per call, no swaps). In general O(n + I) where I is the number of inversions, since every swap removes exactly one. Space O(n) for the recursion stack: f(0) stays on the stack until f(n) returns.

Approach 2: Head recursion, sort the prefix then insert the last element

Intuition. There is a second, equally natural way to see insertion sort recursively, and it is the one in the CLRS textbook: to sort n elements, first sort the first n - 1 recursively, then insert the last one. The recursive call comes before the work, so this is a head recursion, whereas approach 1 does the work first and recurses after.

Both produce the same sequence of insertions, arr[1], then arr[2], and so on, because the deepest call of the head recursion handles the two-element prefix and the insertions happen as the calls unwind. The insertion here uses the shifting technique: hold the element in key, move larger elements right, and write key once.

Algorithm.

1. recursiveInsertionSortHead(arr) starts with n = arr.length.
2. recursiveInsertionSortHead(arr, n): if n <= 1 return.
3. Recursively sort arr[0..n-2].
4. Let key = arr[n - 1] and j = n - 2; while j >= 0 and arr[j] > key, shift arr[j] to arr[j + 1] and j--; finally arr[j + 1] = key.

static void recursiveInsertionSortHead(int[] arr) {
    recursiveInsertionSortHead(arr, arr.length);
}

static void recursiveInsertionSortHead(int[] arr, int n) {
    if (n <= 1) return;
    recursiveInsertionSortHead(arr, n - 1);
    int key = arr[n - 1];
    int j = n - 2;
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = key;
}

Complexity. Time O(n^2) worst, O(n) best, O(n + I) in general, identical to approach 1; the shifting version writes about a third as many array slots as the swapping one. Space O(n) stack. Here the stack reaches its full depth n before any element is moved, since all the recursive calls are made first.

The recurrence for the worst case is T(n) = T(n - 1) + O(n), which unrolls to O(n^2). Compare it with merge sort’s T(n) = 2T(n/2) + O(n): splitting off one element at a time instead of halving is exactly what keeps insertion sort quadratic.

Approach 3: No loops at all

Intuition. The inner while is also a loop that can become a recursion. insert(arr, j) compares arr[j] with its left neighbour; if the neighbour is larger, swap and recurse on j - 1, otherwise stop. The outer function f(i) calls insert(arr, i) and recurses on i + 1. Two recursions, zero loops.

This is the clearest demonstration that a loop is a recursion whose loop variable became a parameter, and of the cost of doing that: an inner stack of depth up to i on top of the outer stack of depth n.

Algorithm.

1. recursiveInsertionSortNoLoops(arr, i): if i >= n return; call insert(arr, i); recurse with i + 1.
2. insert(arr, j): if j <= 0 or arr[j - 1] <= arr[j] return; swap arr[j - 1] and arr[j]; recurse with j - 1.

static void recursiveInsertionSortNoLoops(int[] arr) {
    recursiveInsertionSortNoLoops(arr, 1);
}

static void recursiveInsertionSortNoLoops(int[] arr, int i) {
    if (i >= arr.length) return;
    insert(arr, i);
    recursiveInsertionSortNoLoops(arr, i + 1);
}

static void insert(int[] arr, int j) {
    if (j <= 0 || arr[j - 1] <= arr[j]) return; // reached the front, or the left neighbour is not larger
    int tmp = arr[j];
    arr[j] = arr[j - 1];
    arr[j - 1] = tmp;
    insert(arr, j - 1);
}

Complexity. Time O(n^2) worst, O(n) best. Space O(n): the outer chain has up to n frames and, while insert runs, up to i more; the inner frames are all popped before the next outer call, so the peak is below 2n frames.

Edge cases and pitfalls

• Empty array. Approach 1 starts at i = 0 and 0 >= 0 is the base case; approach 2 has n = 0 <= 1; approach 3 starts at i = 1 >= 0. All return without touching the array.
• Single element. Same base cases; nothing to insert.
• Short-circuit order. j > 0 && arr[j - 1] > arr[j], j >= 0 && arr[j] > key and j <= 0 || arr[j - 1] <= arr[j] all rely on the bounds check being evaluated first. Reverse the operands and you index arr[-1].
• Writing key to j + 1. When the shifting loop in approach 2 stops, j is the index of the element that is <= key (or -1); the hole is at j + 1. Writing to j is the most common insertion sort bug.
• Stability. All three variants move the new element past strictly larger elements only, so equal elements keep their original order.
• Compare directly. arr[j] - key > 0 overflows near the int limits; the tests include Integer.MIN_VALUE and Integer.MAX_VALUE in one array.
• Stack depth. Every variant recurses n deep, so arrays of 10^5 elements risk StackOverflowError with the default JVM stack. The tests use n = 1000. The iterative version has none of this cost, which is why the recursion is a learning exercise rather than a technique to use in production.
• Best case is still linear. On sorted input every insertion stops after one comparison, so even the recursive versions finish in O(n) time; only the O(n) stack remains.

Related problems

• Insertion Sorting is the iterative original with the swapping, shifting and binary-search variants.
• Recursive Bubble Sort applies the same loop-to-recursion transformation to bubble sort.
• Selection Sort and Bubble Sort complete the set of elementary quadratic sorts.
• Merge Sorting shows what happens when the recursion halves the array instead of peeling off one element: O(n log n) instead of O(n^2).