A version of insertion sort that doesn't move records, only keeps 
track of where they would be moved.


int places[n];  // places(i) will be the place in the original record array 
                // occupied by the record with the i-th smallest key. 
 

for i = 1,...,n {           // Insert each element in turn, except the first.
   new_key = record(i).key; // The key of the element to be inserted..
   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 new element.
   while (record(i).key > new_key ) { // Larger elements are moved over.
      places(j+1) = places(j);
      j = j - 1; }  
   places(j+1) = i; // This is where the new record goes.
}         // All done!