Write a recursive procedure for Insertion Sort

Do recursion and after that insert the value.
/*
 * Helper function, Insert val at proper position
 */ 
void insert(int a[], int n, int val)
{
     int i;
     for(i=n-1; i >= 0  && a[i] < val; i--)
                a[i+1] = a[i];
     a[i+1] = val;
}
/*
 * Recursive version of Insertion Sort
 */
void insertRsort(int a[], int n)
{
     if(n>0) {
             insertRsort(a, n-1);
             insert(a, n, a[n]);
     }
}

Sorting List using Insertion Sort

Write a program to sort a list using insertion sort.

/*

 * Node of list

 */

struct node {
       int data;
       struct node* next;
};
typedef struct node* nodeptr;

/*
 * Insert a node into its sorted position
 */
void SortedInsert(nodeptr* head, nodeptr newNode)
{
    nodeptr currentNode = *head;
    nodeptr prevNode = NULL;
    while(currentNode != NULL && currentNode->data < newNode->data) {
        prevNode = currentNode;
        currentNode = currentNode->next;
    }
    newNode->next = currentNode;
    if(prevNode == NULL)
        *head = newNode;
    else
         prevNode->next = newNode;
} 

/* 
 * Insert Sort List
 */
void InsertSort(nodeptr* head)
{
    nodeptr current = *head;
    nodeptr list = NULL;
    nodeptr next = NULL;
    while(current!= NULL)
    {
        next = current->next;
        SortedInsert(&list,current);
        current = next;
    }
    *head = list;
}

Insertion Sort

An insertion sort is one that sorts a set of records by inserting records into an existing sorted file.

Below is the insertion sort procedure code

void InsertionSort(int x[],int n)
{
    int i,k,y;
    for(k=1;k<n;k++)
    {
        y=x[k];
        for(i=k-1;i>=0 && y<x[i];i--)
            x[i+1] = x[i];
        x[i+1]=y;
    }
}

Time complexity iss O(n2) if the file is initially sorted in reverse order. On average case also its time complexity is O(n2).