C program to implement recursive insertion sort

Recursive insertion sort in C: In this tutorial, we will learn how to implement recursive insert sort to sort array elements with the help of the C program? By Sneha Dujaniya Last updated : August 03, 2023

Problem statement

Given an array of integer elements, we have to sort array elements using recursive insertion sort.

C program to implement recursive insertion sort

#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;
}

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

    rec_insertion(arr, n);

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

    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.