# Program Code For Recursive Insertion Sort

Iterative insertion sort is very common. In this post, the recursive insertion sort is given.

[code language="C"] void recursiveInsertionSort(int *a, int k, int key){ if(k<0){ //if index is <0 which means indexes are over a[0] = key; return; } if(a[k] > key){ a[k+1] = a[k]; recursiveInsertionSort(a, k-1, key); return; } else{ a[k+1] = key; return; } } [/code]

I would encourage you to write the driver program yourself by understanding the recursiveInsertionSort() function implementation. A hint is given below.

[code language="C"] ... for(i=1; i<n; i++){ //i is the index of array | a[i] is the Key k = i - 1; recursiveInsertionSort(a, k, a[i]); //args: array | index | key } ... [/code]