CSC151 2007S, Class 45: Insertion Sort

Admin:
* EC for tonight's Sociology Talk (Quantitative Sociology).
* Are there questions on HW15?
* We'll spend a few minutes looking at HW14.
  * Discussion of HW13 delayed another day or two.

Overview:
* Preparation.
* Lab.
* Reflection.

Insertion Sort:
* Key idea of insertion sort:
  * Sort by repeatedly inserting something into the right place in a list
* We can repeatedly insert into a list
* We sometimes also sort vectors
  * Mentally divide the vector into sorted stuff (at the left)
    and unsorted stuff (at the right)
  * Repeatedly take the leftmost thing in unsorted and swap it left.