What is this sort called?

[Stefan Koch]

Hi,

I've come across a sorting algorithm ato build up a sorted array 
and I am not sure what it's called.
Perhaps someone here knows what the name of it is.

It goes like this:

  - assume it already sorted
  - compare the element against the highest element we have seen 
so far, if it's
    higher put the incoming element to the right and continue.
  - if it's not higher we have to search for the place where it 
goes
       - for the search we first check if it's higher than the 
last record that did not come in order, if it is than that's were 
we start our search. if it's not we start searching from the 
beginning of the array.
    once we have found the index where the value needs to be 
inserted we copy all the records that are to the right of it. one 
position to the right, and stick in our value, then we update the 
index of the last record that did not come in order and continue.

or in psedocode:

```d
void insertSorted (Record[] records, Record r, SortState* s)
{
   if (r.value > records[$-1].value)
   {
      records ~= r;
   }
   else
   {
      int ourPlace = 0;
      if (records[s.lastUnsortdedElementIndex].value < r.value)
      {
         ourPlace = s.lastUnsortedElementIndex;
      }
      while(records[ourPlace].value < r.value)
      {
         ourPlace++;
      }
      // after the while loop is done ourPlace is the index at 
which we should go
      {
         records.length = records.length + 1;
         //everyone to the right of our place move one further.
         foreach(i; ourPlace .. records.length -1)
         {
           records[i+1] = records[i];
         }
         records[ourPlace] = r;
         s.lastUnsortedElementIndex = ourPlace;
      }
   }
}
```

I am fascinated by this because it seems to perform so poorly 
once the initial assumption is violated.
However how poor it performs is directly linked to the amount of 
disorder in the incoming stream.