Java Program for Recursive Insertion Sort

Last Updated : 14 Mar, 2023

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.Below is an iterative algorithm for insertion sort

Algorithm

// Sort an arr[] of size n insertionSort(arr, n) Loop from i = 1 to n-1. a) Pick element arr[i] and insert it into sorted sequence arr[0..i-1]

Java

// Recursive Java program for insertion sort import java.util.Arrays; public class GFG  {  // Recursive function to sort an array using  // insertion sort  static void insertionSortRecursive(int arr[], int n)  {  // Base case  if (n <= 1)  return;    // Sort first n-1 elements  insertionSortRecursive( arr, n-1 );    // Insert last element at its correct position  // in sorted array.  int last = arr[n-1];  int j = n-2;    /* Move elements of arr[0..i-1], that are  greater than key, to one position ahead  of their current position */  while (j >= 0 && arr[j] > last)  {  arr[j+1] = arr[j];  j--;  }  arr[j+1] = last;  }    // Driver Method  public static void main(String[] args)  {  int arr[] = {12, 11, 13, 5, 6};    insertionSortRecursive(arr, arr.length);    System.out.println(Arrays.toString(arr));  } }

JavaScript

// Recursive JavaScript program for insertion sort function insertionSortRecursive(arr, n) { // Base case if (n <= 1) { return; } // Sort first n-1 elements insertionSortRecursive(arr, n - 1); // Insert last element at its correct position // in sorted array. const last = arr[n - 1]; let j = n - 2; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > last) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = last; } // Driver Method const arr = [12, 11, 13, 5, 6]; insertionSortRecursive(arr, arr.length); console.log(arr);