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]