#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;
}