array out of range in 'Introsort.mqh' (225,23)

[amrali]

When including the header <Generic\ArrayList.mqh> I have encountered an array out of range in 'Introsort.mqh'

I had to replicate that error using this script:

#include <Generic\ArrayList.mqh>

int test_array[];

void OnStart()
  {
   int size = 1e7; // 10 millions
   ArrayResize(test_array, size);
   Print("array size = ",size);

   while(!IsStopped())
     {
      RandomFill(test_array);
      //--- create source list from array
      CArrayList<int> list(test_array);
      //--- sort the list (Introsort algorithm)
      list.Sort();
      //--- copy data back from the list
      list.CopyTo(test_array);

      Sleep(10);
     }
  }

void RandomFill(int &arr[])
  {
   int size = ArraySize(arr);
   for(int i = 0; i < size; i++)
     {
      //--- 90% of the data is in order and the unsorted elements are evenly distributed.
      //--- An example use-case would be re-sorting an already sorted list after minor modifications.
      if(MathRand() / 32768. < 0.9)
         arr[i] = i;
      else
         arr[i] = MathRand();
     }
  }

This is the output after a short time of running the script

This is the corrected code for <Generic\Internal\introsort.mqh> (line 221) to fix the array out of range error.

template<typename TKey,typename TItem>
void Introsort::DownHeap(int i,const int n,const int lo)
  {
   TKey d=keys[lo+i-1];
   //TItem dt=items[lo+i-1];
   TItem dt=(ArraySize(items)!=NULL) ? (TItem)items[lo+i-1] : (TItem)NULL;
   int child;
   while(i<=n/2)
     {
      child=2*i;
      if(child<n && comparer.Compare(keys[lo+child-1],keys[lo+child])<0)
        {
         child++;
        }
      if(!(comparer.Compare(d,keys[lo+child-1])<0))
        {
         break;
        }
      keys[lo+i-1]=keys[lo+child-1];
      //if(true)//(items!=NULL)
      if(ArraySize(items)!=NULL)
        {
         items[lo+i-1]=items[lo+child-1];
        }
      i=child;
     }
   keys[lo+i-1]=d;
   if(ArraySize(items)!=NULL)
     {
      items[lo+i-1]=dt;
     }
  }

[Alain Verleyen]

Confirmed and reported.

[amrali]

Alain Verleyen #:
Confirmed and reported.

Thanks Alain!