Another version of the insertion sort algorithm.  This one accesses
the underlying records only at the beginning.  It has O(n) accesses
rather than O(n^2) accesses for the previous versions.  If desired, 
you could add code to rearrange the records according to the 
key_record.place fields that this code fragment has made.  This code
also uses the <- notation to distinguish between assignment of
primative data types (integer or float) and assignment objects of 
complex data type (in this case, a not very complex structure).


struct key_record { // Keep track only of the key and ...
   int place;       // which record it belongs to.
   float key; }

key_record keys[n];  // An array to put the keys into.

for i = 1, ..., n {                 
   keys(i).key   = record[i].key;   // Copy out the keys from the records ...
   keys(i).place = i; }             // and remember where they came from.
 

for i = 1,...,n {  // Insert each element in turn, except the first.

   new_key   = keys(i).key;   // The key of the new element to be inserted.
   new_place = keys(i).place; // The place it came from.

   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 the pointer being inserted.
   while (keys.key(j) > new_key ){ // Elements larger are moved over.
      a(j+1) = a(j);
      keys(j+1) <- keys(j); // Copy the record.  
      j = j - 1; }  
   keys(j+1).key   = new_key; // This is where the new record pointer goes.
   keys(j+1).place = new_place;
}         // All done!