Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Recursive Insertion Sort in Java: Sort the Prefix, Insert the Last Value

Implement insertion sort with no loops, use separate recursive sorting and shifting helpers, and explain stability, the return phase and stack cost.

EasyRecursion and backtrackingPattern: recursion

Problem statement

Sort the same array in nondecreasing order using recursion only. No for/while loops and no built-in sorting are allowed in the solution. Duplicate and negative values are valid.

The supplied task permits 1–1000 values from −10,000 to 10,000. GFG’s recursive insertion-sort reference explains prefix recursion but uses a loop for insertion. Our version recursively performs that step too, meeting the stricter supplied contract. The display call Arrays.toString is not sorting.

There was no corresponding insertion-sort implementation in the supplied recursion folder. This method is an original companion solution, using the same smaller-problem reasoning as your other examples.

Constraints & requirements

CONTRACT
Original task: 1–1000 integers from −10,000 to 10,000, including duplicates. Both prefix sorting and shifting must be recursive. The GFG resource explains the pattern but its insertion loop is not this stricter no-loop contract.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    [7,4,1,5,3]
    Output
    [1,3,4,5,7]

    Each returned call inserts one last value into an already sorted prefix.

  2. Example 2 Case 2

    Input
    [5,4,4,1,1]
    Output
    [1,1,4,4,5]

    Strictly larger predecessors shift; equal values keep their relative order.

  3. Example 3 Case 3

    Input
    [-2]
    Output
    [-2]

    A length-one prefix is already sorted.

Read on GeeksforGeeks ↗

Hints Optional

Hints become more specific one step at a time.
01Hint 1

Assume recursion can sort the first n−1 elements.

02Hint 2

Save the last value, then shift larger predecessors right.

03Hint 3

Use a second recursive helper for shifting so no while loop remains.

How to think before coding

Define sortPrefix(a,n) to sort exactly the first n elements. A prefix of length at most one is finished. First sort n−1 elements, then insert the saved last value into that sorted prefix. Define a second helper to move strictly larger predecessors right until the gap is correct. The strict comparison preserves equal-value order.

Brute force and the improvement

Ordinary iterative insertion sort grows a sorted prefix, shifting larger values right to insert the last value. It takes O(n²) worst-case time and O(1) extra space, but loops are forbidden in this particular task. Preserve the same idea and express BOTH the prefix pass and the shifting pass recursively. This satisfies the restriction, not a faster worst-case bound: recursive frames add O(n) extra space. A built-in sort would bypass the exercise rather than solve its no-loop requirement.

Intuition: trust a sorted smaller prefix

To sort [7,4,1], first sort [7,4]. Recursion returns [4,7,1]; now insert the final 1 into its proper place among 4 and 7.

Save 1 in a local variable before shifting. Move 7 right, then 4 right, then place 1 into the vacant first slot. If the saved value were left only in the array, a shift would overwrite it.

Two helpers have different responsibilities: sortPrefix decreases the prefix length; insertIntoPrefix moves left through the already sorted prefix. Neither needs a loop.

Algorithm

  1. A prefix of length zero or one is already sorted.
  2. Recursively sort the first length−1 values.
  3. Save the next value at position length−1.
  4. Recursively shift larger predecessors one place right.
  5. Stop at the start or a predecessor no larger than the saved value, then fill the open slot.

Java solution

Both growing the sorted prefix and shifting larger predecessors use recursive helpers. No loop or built-in sort is used.

Java
import java.util.*;

class Solution {
    public static int[] insertionSort(int[] nums) {
        sortPrefix(nums, nums.length); // Modify the same array; no loops or built-in sorting here.
        return nums;
    }
    private static void sortPrefix(int[] nums, int length) {
        if (length <= 1) return; // Zero or one element is already sorted.
        sortPrefix(nums, length - 1); // Trust the smaller call to sort the earlier prefix.
        int value = nums[length - 1]; // Keep the next value safe before shifts overwrite its position.
        insertIntoPrefix(nums, length - 2, value); // Place it inside the now-sorted prefix.
    }
    private static void insertIntoPrefix(int[] nums, int index, int value) {
        if (index < 0 || nums[index] <= value) { // At start, or just after a value no larger than ours.
            nums[index + 1] = value; // Fill the one open slot; equality stays before the new equal value.
            return;
        }
        nums[index + 1] = nums[index]; // Move a larger predecessor one place right.
        insertIntoPrefix(nums, index - 1, value); // Recursively continue shifting; no while loop.
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(insertionSort(new int[]{7, 4, 1, 5, 3}))); // [1, 3, 4, 5, 7]
    }
}

The driver prints [1,3,4,5,7]. The solution contains no loops and returns the same array object, not a sorted replacement.

Call chain and dry run

Numbered illustrated dry run for Recursive Insertion Sort; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

Follow the Java, step by step

Example: nums = [3,1,2]

What to track: Track length in sortPrefix, and index/value in insertIntoPrefix. value is saved before shifting overwrites its old array position.

  1. Sort the smaller prefix first

    Java operationsortPrefix(nums, length - 1);
    Statewaiting calls have length = 3 and 2; the length = 1 call returns; nums = [3,1,2]

    The first element alone is sorted. No shift happens during this descent.

  2. Save the next value

    Java operationint value = nums[length - 1];
    Stateresumed length = 2 frame: value = 1; insert index = 0

    The earlier prefix [3] is now sorted. Keep 1 safe before shifting 3 into its slot.

  3. Shift the larger predecessor

    Java operationnums[index + 1] = nums[index];
    State3 > 1; nums = [3,3,2]; recursive insert receives index = -1, value = 1

    The temporary duplicate 3 is expected. The saved local value still contains 1.

  4. Fill the open first slot

    Java operationnums[index + 1] = value;
    Stateindex = -1; nums[0] = 1; nums = [1,3,2]

    The recursive shift has reached the start. Returning leaves a sorted prefix of length 2.

  5. Insert the final value

    Java operationint value = nums[length - 1];
    Stateresumed length = 3: value = 2; insert index = 1; 3 shifts right; nums = [1,3,3]

    The earlier call is fully finished before the length-3 frame reads its value.

  6. Stop after the smaller predecessor

    Java operationif (index < 0 || nums[index] <= value)
    Statenext index = 0; nums[0] = 1 ≤ 2; write nums[1] = 2; nums = [1,2,3]

    No further shift is needed. The same recursive rule performs what the usual inner while loop would do.

Final result: [1,2,3] in the same input array.

Worked example · read from top to bottom
sortPrefix([7,4,1], 3)
  → sortPrefix(..., 2)
    → sortPrefix(..., 1) → base return
  insert 4: save 4, shift 7 right, put 4 at index 0
  array is now [4,7,1]
insert 1: save 1, shift 7, shift 4, put 1 at index 0
array is now [1,4,7]
Inserting 1 Array Saved value
Start [4,7,1] 1
Shift 7 [4,7,7] 1
Shift 4 [4,4,7] 1
Fill position 0 [1,4,7] 1

Temporary duplicate entries during shifting are expected: the saved variable holds the displaced value until its slot is filled. Checking the array halfway through a shift does not describe the final sorted result.

Why it works

By induction, the smaller call returns a sorted prefix. Insertion shifts precisely the suffix of values larger than the saved one. The remaining predecessor is no larger, so filling the next slot preserves nondecreasing order and all values. Repeating this argument until the whole array is the prefix proves correctness.

The comparison uses <= to stop before shifting equal predecessors. That preserves their original relative order, so the algorithm is stable. Integers alone do not reveal identity, but the argument also applies to equal-key records with this same comparison rule.

Complexity and alternative approaches

Worst-case time is O(n²): reverse-sorted input shifts 1+2+…+(n−1) values. Already sorted input takes O(n) because each insertion stops immediately. Recursive auxiliary space is O(n), not O(1); Java does not eliminate this call chain.

The sorting and insertion stacks can coexist, but total live depth remains O(n): a short prefix insertion happens while some larger-prefix callers are waiting. They do not multiply into n² live frames.

Iterative insertion sort has the same comparison behavior with O(1) auxiliary space, but violates this task’s no-loop requirement. Merge sort has O(n log n) time but is not insertion sort. Use those as tradeoffs, not as interchangeable submissions.

Common mistakes

  • Leaving a while loop in the insertion helper.
  • Reading the last value after shifting has already overwritten it.
  • Shifting equal values and losing stability.
  • Returning before insertion after the smaller prefix finishes.
  • Calling recursion constant-space merely because it sorts in place.

Practice next

Next lessonPow(x,n)

Back to Recursion and backtracking →