//+------------------------------------------------------------------+
//|                                                    Introsort.mqh |
//|                                        Copyright © 2018, Amr Ali |
//|                             https://www.mql5.com/en/users/amrali |
//+------------------------------------------------------------------+

//+------------------------------------------------------------------+
//| Introsort                                                        |
//+------------------------------------------------------------------+
/**
 * Sort the input array in-place using comparison function less.
 * You can specify your own comparison function. If no function is
 * specified, ascending sort is used.
 *
 * Generally, the fastest comparison-based sort algorithm for arrays.
 * (esp. if large size).
 * Average time complexity: O(n log n)
 * Worst-case time complexity: O(n log n)
 * Stable    : no
 *
 * Introsort is a hybrid sorting algorithm that uses three sorting algorithm
 * to minimise the running time: Quicksort, Heapsort and Insertion Sort.
 * Introsort begins with quicksort and if the recursion depth goes more
 * than a particular limit it switches to Heapsort to avoid Quicksort’s
 * worst case O(N2) time complexity. It also uses insertion sort when the
 * number of elements to sort is quite less.
 */
template<typename T>
void Introsort(T &arr[])
  {
   Introsort(arr, 0, ArraySize(arr) - 1);
  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
template<typename T>
void Introsort(T &arr[], int lo, int hi)
  {
   int size = hi - lo + 1;
   int depthLimit = 2 * (int)MathFloor(MathLog(size)/M_LN2);
   IntrosortInternal::IntrosortUtil(arr, lo, hi, depthLimit);
  }

namespace IntrosortInternal
{
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
/**
 * depthLimit:
 * It represents maximum depth for recursion. It is typically chosen
 * as log of length of input array. The idea is to ensure that the worst
 * case time complexity remains O(N log N).
 */
template<typename T>
void IntrosortUtil(T &arr[], int lo, int hi, int depthLimit)
  {
   const int InsertsortSizeThreshold = 16;
   while(lo < hi)
     {
      int partitionSize = hi - lo + 1;
      //--- Insertion sort is faster for small partitions.
      if(partitionSize <= InsertsortSizeThreshold)
        {
         InsertionSort(arr, lo, hi);
         return;
        }
      //--- If recursion depth exceeds limit, switch to heapsort to guarantee O(n log n).
      if(--depthLimit == 0)
        {
         HeapSort(arr, lo, hi);
         return;
        }

      //--- Pick pivot as the median-of-three.
      T pivot = Median3(arr, lo, hi);

      //--- Hoare’s partitioning scheme.
      int p = partition(arr, lo, hi, pivot);

      //--- Sort the left partition first using recursion and do tail recursion elimination for
      //--- the right-hand partition.
      IntrosortUtil(arr, lo, p - 1, depthLimit);
      lo = p;
     }
  }
//+------------------------------------------------------------------+
//| partition subarray a[lo..hi] around pivot and return pivot index.|
//+------------------------------------------------------------------+
template<typename T>
int partition(T &arr[], int lo, int hi, T& pivot)
  {
   while(lo <= hi)
     {
      while(Less(arr[lo], pivot)) lo++;
      while(Less(pivot, arr[hi])) hi--;
      if(lo > hi)
         break;
      Swap(arr[lo++], arr[hi--]);
     }
   return lo;
  }
//+------------------------------------------------------------------+
//| Insertion Sort                                                   |
//+------------------------------------------------------------------+
template<typename T>
void InsertionSort(T &arr[], int lo, int hi)
  {
   for(int i = lo + 1; i <= hi; i++)
     {
      if(Less(arr[i], arr[i - 1]))
        {
         T curr = arr[i];
         arr[i] = arr[i - 1];
         int j = i;
         while(--j > lo && Less(curr, arr[j - 1]))
            arr[j] = arr[j - 1];
         arr[j] = curr;
        }
     }
  }
//+------------------------------------------------------------------+
//| Heap Sort                                                        |
//+------------------------------------------------------------------+
template<typename T>
void HeapSort(T &arr[], int lo, int hi)
  {
   int size = hi - lo + 1;
   for(int i = size / 2 - 1; i >= 0; i--)
     {
      Heapify(arr, i, size, lo);
     }
   for(int i = size - 1; i > 0; i--)
     {
      Swap(arr[lo], arr[lo + i]);
      Heapify(arr, 0, i, lo);
     }
  }
//+------------------------------------------------------------------+
//| Rebuilds the heap.                                               |
//+------------------------------------------------------------------+
template<typename T>
void Heapify(T &arr[], int parent, int heap_size, int lo)
  {
   T temp = arr[lo + parent];
   int child = parent * 2 + 1;
   while(child < heap_size)
     {
      if(child + 1 < heap_size && Less(arr[lo + child], arr[lo + child + 1]))
        {
         child++;
        }
      if(!Less(temp, arr[lo + child]))
        {
         break;
        }
      arr[lo + parent] = arr[lo + child];
      parent = child;
      child = parent * 2 + 1;
     }
   arr[lo + parent] = temp;
  }
//+------------------------------------------------------------------+
//| Get the median of three array elements.                          |
//+------------------------------------------------------------------+
template<typename T>
T Median3(T &arr[], int lo, int hi)
  {
   int mid = lo + (hi - lo) / 2;
   Sort3(arr, lo, mid, hi);
   return arr[mid];
  }
//+------------------------------------------------------------------+
//| Sorts the elements a, b and c using comparison function less.    |
//+------------------------------------------------------------------+
template<typename T>
void Sort3(T &xs[], int a, int b, int c)
  {
   Sort2(xs, a, b);
   Sort2(xs, b, c);
   Sort2(xs, a, b);
  }
//+------------------------------------------------------------------+
//| Sorts the elements a and b using comparison function less.       |
//+------------------------------------------------------------------+
template<typename T>
void Sort2(T &xs[], int a, int b)
  {
   if(Less(xs[b], xs[a]))
      Swap(xs[a], xs[b]);
  }
//+------------------------------------------------------------------+
//| Swaps two array elements using references.                       |
//+------------------------------------------------------------------+
template<typename T>
void Swap(T& a, T& b)
  {
   T temp = a;
   a = b;
   b = temp;
  }
}

//+------------------------------------------------------------------+
//| Generic comparison function Less.                                |
//+------------------------------------------------------------------+
template<typename T>
bool Less(const T left,const T right)
  { return left < right;  }


//+------------------------------------------------------------------+
//| Custom comparison function Less.                                 |
//+------------------------------------------------------------------+
/*
  You can specify your own comparison function. If no function is
  specified, ascending sort is used.

  A custom Less() function takes two arguments and contains logic to
  decide their relative order in the sorted array. The idea is to
  provide flexibility so that Introsort() can be used for any type
  (including user defined types) and can be used to obtain any
  desired order (increasing, decreasing or any other).

  For example, to sort an array of strings in a descending order:

     bool Less(const string left, const string right)
       { return left > right;  }


  To sort an array of objects or structures (user defined types)
  in a custom sort order:

     bool Less(const CObject& left, const CObject& right)
       {
        if(left.a < right.a) return(true);
        if(left.a > right.a) return(false);
        ...
        ...
       }
*/