//+------------------------------------------------------------------+
//|                                                    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[])
  {
   //--- use default Less function
   typedef bool (*LessFunc)(const T, const T);
   Introsort(arr, (LessFunc)IntrosortInternal::Less<T>);
  }
//+------------------------------------------------------------------+
//| Introsort using a pointer to custom Less() function.             |
//| 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 like objects or structures)   |
//| and can be used to obtain any desired sort order (ascending,     |
//| descending or custom order of structure fields).                 |
//+------------------------------------------------------------------+
template<typename T, typename LessFunc>
void Introsort(T &arr[], LessFunc pfnLess)
  {
   IntrosortInternal::IntrosortUtil(arr, 0, ArraySize(arr) - 1, pfnLess);
  }

namespace IntrosortInternal
{
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
template<typename T, typename LessFunc>
void IntrosortUtil(T &arr[], int lo, int hi, LessFunc pfnLess)
  {
   int size = hi - lo + 1;
   int depthLimit = 2 * (int)MathFloor(MathLog(size)/M_LN2);
   IntrosortUtil(arr, lo, hi, depthLimit, pfnLess);
  }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
/**
 * 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, typename LessFunc>
void IntrosortUtil(T &arr[], int lo, int hi, int depthLimit, LessFunc pfnLess)
  {
   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, pfnLess);
         return;
        }
      //--- If recursion depth exceeds limit, switch to heapsort to guarantee O(n log n).
      if(--depthLimit == 0)
        {
         HeapSort(arr, lo, hi, pfnLess);
         return;
        }

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

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

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

}
//+------------------------------------------------------------------+