C program to implement Recursive Insertion Sort

Here, we are implementing C program to sort array elements using the recursive insertion sort.
Submitted by Sneha Dujaniya, on June 19, 2020

The only difference between Insertion sort and Recursive Insertion Sort is that in the Recursive method, we start from placing the last element in its correct position in the sorted array instead of starting from the first.

Here, I will only be showing the C implementation of the sort as I have explained the basic theory in my previous article.

Recursive Insertion Sort Implementation:

#include <stdio.h>

void rec_insertion(int arr[], int n)
{
    // When the elements are all over
    if (n <= 1)
        return;

    // sorting n-1 elements
    rec_insertion(arr, n - 1);

    int last = arr[n - 1];
    int j = n - 2;

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

    printf("\nAfter performing Insertion sort:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
}

int main()
{
    int arr[] = { 10, 14, 3, 8, 5, 12 };
    int n = sizeof(arr) / sizeof(arr[0]);

    rec_insertion(arr, n);

    return 0;
}

Output:

After performing Insertion sort:
10 14
After performing Insertion sort:
3 10 14
After performing Insertion sort:
3 8 10 14
After performing Insertion sort:
3 5 8 10 14
After performing Insertion sort:
3 5 8 10 12 14

This output shows the array after each i^th iteration. Feel free to ask your doubts.

Top MCQs

Comments and Discussions!