Give a recursive version of the algorithm InsertionSort that

Give a recursive version of the algorithm Insertion-Sort that works as follows: To sort A[1::n], we sort A[1::n - 1] recursively and then insert A[n] in its appropriate position. Write a pseudocode for this recursive version of Insertion Sort and analyze its running time by giving a recurrence relation and solving it.

Solution

void insertion( int e,int *x, int start, int end)
     {
         if (e >= x[end])
             x[end+1] = e;
         else if (start < end)
         {
             x[end+1] = x[end];
            insertion(e, x, start, end-1);
        }
        else
        {
          x[end+1] = x[end];

            x[end] = e;
        }
    }
  
void insertion_recurssion(int *b, int start, int end)

    {
     if(start < end)

        {
            insertion_sort_recur(b, start, end-1);
            insertion(b[end], b, start, end-1);
    }
    }

    void main()

    {
        insertion_recurssion(x,0,5);
    }