Recursive Insertion Sort Program with Explanation and Code

2025-11-02 recursive insertion sort sorting algorithms python c c# js php

Learn how Recursive Insertion Sort works using a clear explanation and detailed step-by-step algorithm. Includes complete program examples in Python, C, JavaScript, PHP, and C#. Ideal for students, beginners, and coding interviews.

Program Explanation

What is Recursive Insertion Sort?

Recursive Insertion Sort is a variation of the traditional Insertion Sort algorithm, implemented using recursion instead of loops. It sorts the array by recursively sorting the first n-1 elements and then inserting the last element into its correct position.

Steps to Solve

  1. Start with the full array length n.
  2. Recursively sort the first n–1 elements.
  3. Store the last element as key.
  4. Compare key with the previous elements.
  5. Shift elements greater than key to the right.
  6. Insert key in the correct sorted position.
  7. Once recursion completes, the entire array will be sorted.

Explain The Program Line By Line (Algorithm)

  1. Define a recursive function that takes the array and current size n.
  2. If n ≤ 1, return because a single element is already sorted.
  3. Recursively call the function for n–1 elements.
  4. Store the nth element as key.
  5. Find the correct location for key among previously sorted elements.
  6. Shift all elements larger than key to one position ahead.
  7. Place key into its sorted position.
  8. Continue until the entire array becomes sorted.

Key Points

  • Recursive Insertion Sort works by solving a smaller problem first.
  • Time complexity is same as normal Insertion Sort: O(n²).
  • Efficient for nearly sorted arrays.
  • Uses call stack instead of loops.
  • Helpful for understanding recursive problem-solving.

Program Code


def recursive_insertion_sort(arr, n):
    if n <= 1:
        return

    recursive_insertion_sort(arr, n - 1)

    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

arr = list(map(int, input("Enter numbers: ").split()))
recursive_insertion_sort(arr, len(arr))
print("Sorted array:", arr)
      

#include <stdio.h>

void recursiveInsertionSort(int arr[], int n) {
    if (n <= 1)
        return;

    recursiveInsertionSort(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;
}

int main() {
    int n, i;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter numbers: ");
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    recursiveInsertionSort(arr, n);

    printf("Sorted array: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}
      

function recursiveInsertionSort(arr, n) {
  if (n <= 1) return;

  recursiveInsertionSort(arr, n - 1);

  let key = arr[n - 1];
  let j = n - 2;

  while (j >= 0 && arr[j] > key) {
    arr[j + 1] = arr[j];
    j--;
  }

  arr[j + 1] = key;
}

let arr = prompt("Enter numbers:").split(" ").map(Number);
recursiveInsertionSort(arr, arr.length);
console.log("Sorted array:", arr);
      

using System;

class Program {

    static void RecursiveInsertionSort(int[] arr, int n) {
        if (n <= 1)
            return;

        RecursiveInsertionSort(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;
    }

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        RecursiveInsertionSort(arr, arr.Length);

        Console.Write("Sorted array: ");
        foreach (int num in arr)
            Console.Write(num + " ");
    }
}
      

<?php

function recursiveInsertionSort(&$arr, $n) {
    if ($n <= 1)
        return;

    recursiveInsertionSort($arr, $n - 1);

    $key = $arr[$n - 1];
    $j = $n - 2;

    while ($j >= 0 && $arr[$j] > $key) {
        $arr[$j + 1] = $arr[$j];
        $j--;
    }

    $arr[$j + 1] = $key;
}

$arr = explode(" ", readline("Enter numbers: "));
recursiveInsertionSort($arr, count($arr));

echo "Sorted array: " . implode(" ", $arr);

?>
1