## Jul 30, 2014

### C Programming Challenge #06: Sort - insertion (using recursion)

We have already covered the insertion sort C Programming Challenge #02: Sort - insertionChallenge is to implement it using recursion.

Recursive definition of insertion sort is

• In order to sort a to a[n] we first sort a to a [n -1] and then insert a[n] into sorted array.
• Trivial solution is when n = 0, no need to sorted. Array of 1 element is always sorted.
Solution would look as follows.

#include <stdio.h>


#define NUM_ELE(a) sizeof(a)/sizeof(a)

int sort_insert(int *, int);
void print_array(int *, int);

int main()
{
int i;
int a[] = {4, 5, 1, 2};

printf("Unsorted Array is - ");
print_array(a, NUM_ELE(a));
printf("\n");

sort_insert(a, NUM_ELE(a) - 1);

printf("Sorted Array is - ");
print_array(a, NUM_ELE(a));
printf("\n");
}
int sort_insert(int *arr, int n)
{
int i;
int cur_card;
if(n >= 1) {
/* First sort array from arr to arr[n - 1] */
sort_insert(arr, n - 1);
/* Following code is to insert arr[n]
into sorted array of arr tp arr[n - 1] */
cur_card = arr[n];
i = n - 1;
while(i >= 0 && arr[i] > cur_card) {
arr[i + 1] = arr[i];
i--;
}
arr[i + 1] = cur_card;
}
return 0;
}
void print_array(int *arr, int n)
{
int i;
for(i = 0; i < n; i++) {
printf(" %d", arr[i]);
}
}


Output is as expected

Unsorted Array is -  4 5 1 2
Sorted Array is -  1 2 4 5