Give a recursive version of the algorithm Insertion-Sort (refer to page 18 in the textbook) 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 InsertionSort and analyze its running time by giving a recurrence relation and solving it

see explaination

Explanation:

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);

}