10/12/2015 - 8:00 AM

Recursive C Insertion Sort

Recursive C Insertion Sort

#define ARR_SIZE 6

void print_r(int *arr, size_t n);
void insertion_sort(int *arr, size_t n, size_t i);

int main(){
    int nums[ARR_SIZE] = {2,8,9,0,0,2};
    print_r(nums, ARR_SIZE);

    insertion_sort(nums, ARR_SIZE, 0);
    print_r(nums, ARR_SIZE);

    return 0;

void print_r(int *arr, size_t n){
    int i;
    for(i=0; i<n; i++){
        printf("\t[%d] => %d\n", i, arr[i]);

 * This insertion sort will be done in place as opposed to the PHP
 * implementation.
void insertion_sort(int *arr, size_t n, size_t i){
    int el,j;

    if(i == n-1){
        // Nothing to do since we're looking at the last element.
        insertion_sort(arr, n, i+1);
        el = arr[i];

        // All elements to the right of index i are assumed to be sorted.
        // Now we just have to figure out where el fits in the sorted array
        for(j = i+1; j<n; j++){
            if(el > arr[j]){
                // el is bigger, swap so el moves to the right in the array.
                arr[j-1] = arr[j];
                arr[j] = el;