Insertion Sort:
_______________

The next sort we look at is the "Insertion". How to remember what this sort does?

Imagine you have the whole suit of diamonds (Ace, 2, 3, 4, ...., Jack, Queen, King)
in your left hand, but they are not in order.

You want to have them in order in your left hand, so you can play a card game. 

To keep it simple, say you only have 5 cards in your hand, exactly this:


   King     Jack     Queen   Ace   3     [treat Ace's value as 1]

Compare the first two and get them in order

  Jack     King      Queen   Ace    3      (now first two are in order)

Compare the third and get it in order with respect to the first two.

  Jack    Queen     King     Ace    3     (now first three are in order)

Compare the fourth and get it in order with respect to the first three

  Ace     Jack      Queen    King    3    (now first four are in order)

Compare the fifth and get it in order with respect to the first four

  3        Ace     Jack      Queen  King


Note: At every step we have a sorted sublist. Then we look at the next element
      and squeeze it into it right place in the sorted sublist. This means we
      have to compare this new element to every element in the sorted sublist
      to see where it fits.  

     In pass 1 we compare 2nd element to 1st  (1 comp)

     In pass 2 we compare 3rd element to first two  (2 comps)

    ......

    In pass (n-1) we compare nth element to the first (n-1)    (so n-1  comparisons)

  Total work = 1 + 2 + 3 + 4 + ...... + (n-1)

             = (n-1)*n/2 ,  which again is an O(n^2) algorithm

  So the number of comparisons is the same as the "find min each time" sort.

  But this algorithm had a bit more structure. We got elements into their right place
  in a systematic way without having to find the minimum in each sublist.

_________________________________________________________________________

NOTE: Whenever we have to get the "next" element into it right place with respect to
      the previously sorted sublist, we may have to move elements to the right in
      the list, to make a place to insert the "next" element.

      Let's call the "next" element the "key". The key is the next card (recall the
      card example) we have to fit into its right place.

      11    3    2    22    1      key = 3

      To start, key = 3. Does 3 go before 11 or after 11? Well, it has to go before

      11    11   2    22    1      key = 3    (copy 11 over to next position)

      3     11   2    22    1                 (copy key = 3 into vacated position)

     Now first 2 elements are sorted **with respect to each other**

      3     11    2    22    1     key = 2

      3     11    11   22    1     (2 goes before 3, so copy 11 over one place)

      3     3     11   22    1     (copy 3 over one place to make room for key)

      2     3     11   22    1     (copy key into place vacated by 3)

      Now first 3 elements are sorted ** with respect to each other **

      2     3     11   22     1     key = 22

      2     3     11   22     1    (nothing to change, 22 is in right place)

      Now first 4 elements are sorted ** with respect to each other **

      2     3     11   22     1      key = 1

      2     3     11   22     22     copy 22 over one place

      2     3     11   11     22     copy 11 over one place

      2     3      3   11     22     copy 3 over one place

      2     2      3   11     22     copy 2 over one place

      1     2      3   11     22     copy key into spot vacated by 2

     No more keys, so list is sorted.

 Notice that this algorithm had to repeatedly shift sublists to the right, to
 make place for a key if it had to move left. If the key is smaller than all the
 numbers in the sublist, the entire sublist has to be moved right by one place.

 Still, in terms of comparisons it is an O(n^2) algorithm. 
________________________________________________________________________