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:

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.

On Friday, 27 August 2021 at 15:02:59 UTC, Stefan Koch wrote:

        foreach(i; ourPlace .. records.length -1)
        {
          records[i+1] = records[i];
        }

I have been alerted to a rather nasty bug in this transcription.
it only works if you iterate the array in reverse as otherwise,
you'll override all values with records[ourPlace]

I guess foreach_reverse does have a place in the language after all.

On Friday, 27 August 2021 at 15:02:59 UTC, Stefan Koch wrote:

I've attempted to use "the sound of sorting" to visualize what's happening.

https://www.youtube.com/watch?v=NQ5iGTQQ1vY

Ironically without sound :)

On Friday, 27 August 2021 at 15:02:59 UTC, Stefan Koch wrote:

I don't think it has a name, it looks like insertion sort with an ad-hoc optimization that it tries to guess where to insert based on the input being mostly monotonically increasing.

On Friday, 27 August 2021 at 19:25:46 UTC, Dennis wrote:

I was guessing that it's some insertion sort.
Comparing it with a generic insertion sort without the optimization it does quite well.