Example of insertion sort in C

This is an example C program demonstrating "insertion sort".

#include <stdio.h>
#include <string.h>

const char * daredevils[] = {
    "Evel Knievel",
    "Freaky Franky the Visible Man",
    "Penelope Pitstop",
    "Batman AKA Clark Kent, the loudmouthed detective",
    "Ringo Starr AKA Richard Starkey",
    "Brad Pitt",
    "Keano Reeves",
    "Gary Seven",
    "Awful Knoffel",
};

#define n_daredevils (sizeof (daredevils) / sizeof (const char *))

static void print_array (const char ** array, int size)
{
    int i;
    for (i = 0; i < size; i++) {
        printf ("%d: %s\n", i, array[i]);
    }
}

/* Sort the contents of "array" with the number of members "size" case
   insensitively. This implements the insertion sort algorithm on
   pages 80 and 81 of volume 3 of the second edition of "The Art of
   Computer Programming" by Donald E. Knuth, published in 1998. In
   this implementation, R is the same thing as K, and R_i in Knuth's
   notation is array[i], and lower case letters are used
   throughout. */

static void insertion_sort (const char ** array, int size)
{
    int j;
    /* Loop from the second entry to the final one, and put each into
       order, keeping the list from 0 to j in order at all times. */
    for (j = 1; j < size; j++) {
	/* The position we are looking at, which goes from j - 1 to 0
	   as we examine the list to see what item has a lower score
	   than k. */
	int i;
	/* The key we are going to sort. */
	const char * k;
	k = array[j];
	/* Go from j-1 to 0 until we find an entry lower than "k". */
	for (i = j - 1; i >= 0; i--) {
	    if (strcasecmp (array[i], k) < 0) {
		break;
	    }
	    /* Move this entry up by one. */
	    array[i + 1] = array[i];
	}
	/* Put the key which was at "j" into the ordered position
	   found in the above loop, which is i+1 since we subtracted
	   one from i at the end of the above loop. We cannot use
	   array[j] since that was overwritten as the entries were
	   moved up by one in the loop above. */
	array[i + 1] = k;
    }
}

int main ()
{
    printf ("Initially, the array looks like this:\n\n");
    print_array (daredevils, n_daredevils);
    insertion_sort (daredevils, n_daredevils);
    printf ("\nAfter it is sorted, the array becomes\n\n");
    print_array (daredevils, n_daredevils);
    return 0;
}

(download)

The output of the example looks like this:

Initially, the array looks like this:

0: Evel Knievel
1: Freaky Franky the Visible Man
2: Penelope Pitstop
3: Batman AKA Clark Kent, the loudmouthed detective
4: Ringo Starr AKA Richard Starkey
5: Brad Pitt
6: Keano Reeves
7: Gary Seven
8: Awful Knoffel

After it is sorted, the array becomes

0: Awful Knoffel
1: Batman AKA Clark Kent, the loudmouthed detective
2: Brad Pitt
3: Evel Knievel
4: Freaky Franky the Visible Man
5: Gary Seven
6: Keano Reeves
7: Penelope Pitstop
8: Ringo Starr AKA Richard Starkey

See also this Example of quicksort in C. Quicksort is another algorithm for sorting. It is more complex than insertion sort, but for long lists it is quicker.

Acknowledgements: Santosh Shaw from India pointed out that an earlier version of this page did not use a correct insertion sort algorithm since it did not run in O(n) time when the list was already sorted.