```#include <stdio.h>

void p( int a[], int len )
{
for( int i = 0; i < len - 1; i++ )
printf( "%d, ", a[i] ) ;
printf( "%d\n", a[ len - 1 ] ) ;
}

int main()
{
int a[] = { 5, 9, 1, 22, 6, 7, 7, 90 } ;
int len = sizeof( a ) / sizeof( int ) ;  // *note:
// sizeof() doesn't work for pointer (int * a) style arrays

p( a, len ) ;

// The insertion sort algorithm is here, and
// every line is explained in comments.

// UNDERSTANDING INSERTION SORT
// The best analogy for understanding insertion
// sort is if you think of holding a hand of cards.

// Say you have this hand:
// 7, 2, 5, 8

// Now you like to see things in order, so you
// want them to have the order 2, 5, 7, 8.  What's
// the easiest way to order the cards without
// putting them down flat on the table?

// You'd probably do this.  Start at the
// very left hand side.  Skip the first card,
// and PULL OUT the second card
// so now you're looking at the 2.

// In left hand:  7, ___,  5, 8
// In right hand:  2

// (the empty space is where the 2 WAS)

// FROM the place where the 2 WAS,
// work backwards until
// you find where that 2 "SHOULD GO"
// in the GREEN ("already sorted") section.

// Clearly the 2 should go in front of the 7.

// Thinking like a computer...

// To make the 2 go in front of the 7, we have
// to SLIDE the 7 over to occupy the space
// where the 2 WAS:

// In left hand:  ___, 7,  5, 8
// In right hand:  2

// Now we can insert the 2 into that blank spot:

// In left hand:  2, 7,   5, 8
// In right hand:  ___

// You just keep going
// until you INSERT all the cards from the
// UNSORTED section
// into their correct positions in the SORTED section

// Next step:  We're on the 5.

// Pull it out.

// In left hand:  2, 7, ___  8
// In right hand:  5

// WORK BACKWARDS FROM the ___ spot.

// AS WE STEP BACKWARDS,
// we are looking for an entry in
// the already sorted section that
// is SMALLER than the number
// we have plucked out in our right hand
// (the 5 in this case)

// In left hand:  2, 7, ___  8
// ** NO, 7 is not SMALLER than 5.
// So we simply siddle the 7 up

// In left hand:  2, ___, 7  8
// ** YES, 2 is smaller than 5, so
// our 5 will belong right after the
// 2 (where the blank space happens
// to be right now!!)

// We simply insert the 5 here,
// and we are done with the 5.
// In left hand:  2, 5, 7  8

// last step:  remove the 8:

// In left hand:  2, 5, 7, ___

// Start by looking at the 7.  7
// is less than 8, so the 8 goes
// in after the 7 (where it was
// basically)

// In left hand:  2, 5, 7, 8

// And that's the algorithm.

// NOTICE the method you use.  At every card
// you attempt to sort, you count BACKWARDS
// from the place you pulled it out from,
// until you find a number that is SMALLER
// than the card you are trying to insert.

//////////////
// THE C CODE:

// the outer for loop.  the outer loop walks us
// THRU the array, FORWARDS, ONCE.

// In this SINGLE PASS through the array
// we are sorting, at EVERY number we hit
// we will STOP, look back through the
// beginning part of the list, and put that
// number WHERE IT BELONGS.

for( int j = 1;  // start at the SECOND element of the list
j < len ;   // go until the end of the list
j++ )       // one at a time.
{
// { 5, 9, 1, 22, 6, 7, 7, 90 } ;
//     ^^^
//    ( START HERE, not at the very beginning )

// Now, at EACH number you're at
// first, we must SAVE IT OFF.

// Reason:  Its going to be overwritten.
int KEY = a[ j ] ;

// This is equivalent to "pulling
// the card out" in the explanation above.

// Next, we walk BACKWARDS through
// the array, STARTING at the position
// JUST BEFORE the card we "pulled out"

int i ;
for( i = j - 1 ;  // start at position JUST BEFORE item we pulled out
i >= 0 ;     // we'll walk down until the VERY BEGINNING of the list
// ** UNLESS WE FIND A NUMBER IN THE LIST
// THAT IS SMALLER THAN KEY (in which case
// we will BREAK out of this loop)

i-- )        // we're walking backwards thru the list
{
// Now, we are LOOKING FOR
// a number in a[] that is
// SMALLER than the KEY we
// have in our hand.

// Once we find a number that
// is SMALLER than the KEY,
// we will know where to
// insert the KEY (right
// after THAT number which is
// smaller than the KEY.)

// Notice how this assumes that
// everything to the left of the KEY
// IS ALREADY SORTED (which it will be
// as this algorithm works through
// the list).
if( a[ i ] < KEY )
{
// Found spot for KEY.  Stop "siddling"
// (see ELSE statement below for "siddle").

break;
}
else
{
// siddle.  copy element over.

a[ i + 1 ] = a[ i ] ;

// on the first iteration, this
// operation will overwrite the KEY
// in the array (hence the need to
// save it off in a separate variable).
}
}

// Insert the key.
a[ i + 1 ] = KEY ;
}

p( a, len ) ;
}
```