RECURSIVE INSERTION SORT

 INSERTION SORT:

                 Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part. 

EXAMPLE:

 

RECURSION IDEA:

1. Base Case: If array size is 1 or smaller, return.
2. Recursively sort first n-1 elements.
3. Insert last element at its correct position in sorted array.

 

ALGORITHM:

• We are going to mimic the Iterative Insertion sort in the recursive implementation.
• We will create a function which will take the array and current index as input.
• In this function we will iterate through all the elements less than the current index and swap the elements based on the sorting order.
• If the index is less than 1 then will terminate the recursive function. Else we will call the same function recursively with one index less.

 

PSEUDO CODE:

INSERTION-SORT(A,n)

1    if n > 1

2       then INSERTION-SORT(A,n-1)

3            key = A[n]

4            i = n-1

5            while i > 0 and A[i] > key

6                  A[i+1] = A[i]

7                  i = i - 1

8            A[i + 1] = key

 

PROGRAM IN 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));

    }

}