Recursive Insertion Sort in Java
Problem
Insertion sort's own definition is already recursive in spirit — the first n - 1 elements need to be sorted before the nth one can be inserted into its correct place among them.
Given an array of integers, sort it in ascending order using a recursive version of insertion sort.
Java Program
import java.util.Arrays;
public class RecursiveInsertionSort {
static void insertionSort(int[] arr, int n) {
if (n <= 1) return; // base case: 0 or 1 elements are already sorted
insertionSort(arr, n - 1); // sort everything before the last element first
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;
}
public static void main(String[] args) {
int[] arr = {5, 1, 9, 3, 7};
insertionSort(arr, arr.length);
System.out.println(Arrays.toString(arr));
}
}Output
Core Logic
Recursing on the first n - 1 elements before touching the nth one guarantees that prefix is already sorted by the time the nth element needs to be inserted into it.
- 1
insertionSort(arr, n)only considers the firstnelements of the array as the region being sorted. - 2The base case
if (n <= 1) return;stops once that region is down to one element or none, which is trivially sorted. - 3Before doing anything else, the method calls
insertionSort(arr, n - 1)— this is what guarantees the firstn - 1elements are sorted by the time the rest of the method runs. - 4Once that call returns, the same shifting logic as the iterative version slides
arr[n - 1]backward past every larger element until it reaches its correct spot.
[5, 1, 9, 3, 7], the recursion first sorts [5, 1, 9, 3] down to [1, 3, 5, 9] before inserting 7, sliding it past 9 to land at [1, 3, 5, 7, 9].Key Point: The recursive call happens before the insertion step, not after — this ordering is what guarantees a sorted prefix exists to insert into, unlike recursive bubble sort, where the pass happens before the recursive call instead.
Why: The same up-to-n shifts per element happen as in the iterative version, but each recursive call adds its own stack frame, so n frames are alive at the deepest point instead of the iterative version's constant space.