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 caseif (n <= 1) {return;}Â
// Sort first n-1 elementsinsertionSortRecursive(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 aregreater than key, to one position aheadof their current position */while (j >= 0 && arr[j] > last) {arr[j + 1] = arr[j];j--;}arr[j + 1] = last;}Â
// Driver Methodconst arr = [12, 11, 13, 5, 6];Â
insertionSortRecursive(arr, arr.length);Â
console.log(arr); |
Output:-
[5, 6, 11, 12, 13]
Time Complexity: O(n2)
Auxiliary Space: O(1)
Please refer complete article on Recursive Insertion Sort for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
