Recursive Insertion Sort | Java Programs

Output:

*** Recursive Insertion Sort ***

Array Before Insertion Sort:
[12, 11, 13, 5, 6]

Array After Insertion Sort:
[5, 6, 11, 12, 13]

Click Here For Java Online Compiler

Solution:

/**
 *
 * @author Alee Ahmed Kolachi
 */
import java.util.Arrays;

public class RecursiveInsertionSort {

    static void recursiveISort(int array[], int n) {
        if (n <= 1) {
            return;
        }

        recursiveISort(array, n - 1);

        // Insert last element at its correct position
        int last = array[n - 1];
        int j = n - 2;

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

    public static void main(String[] args) {
        System.out.println("*** Recursive Insertion Sort ***" + "\n");
        System.out.println("Array Before Insertion Sort:");
        int array[] = {12, 11, 13, 5, 6};
        System.out.println(Arrays.toString(array));
        System.out.println();
        recursiveISort(array, array.length);
        System.out.println("Array After Insertion Sort:");
        System.out.println(Arrays.toString(array));
    }
}