Code fragment illustrating the insertion sort algorithm coded assuming
that we want to sort records on the basis of one field of the records, the
"key".  I use <- for assignment of records, rather than the usual =, to
emphasize that copying records can be complicated and expensive.  Here, 
a is an array of records of type "record".  The "key" is a field of that 
record, referred to as record.key.  Thus, "a(4).key" is a real number and 
the key of the record a(4).

record a[n];

for i = 1,...,n {  // Insert each element in turn, except the first.
   new_key = a(i).key; // The key of the new element to be inserted.
   new_a  <- a(i);     // Store the record so it isn't overwritten.
   j  = i-1;  // j runs through the elements already inserted and in order.
              // Move the sorted elements to the right one by one until
              // you find the spot for new_a.
   while (a(j).key > new_key ) { // Elements larger than new_a are moved over.
      a(j+1) <- a(j);
      j = j - 1; }  
   a(j+1) <- new_a; // This is where new_a goes.
}         // All done!