//+------------------------------------------------------------------+
//|                                                         Sort.mqh |
//|                                  Copyright 2026, Niquel Mendoza. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2026, Niquel Mendoza."
#property link      "https://www.mql5.com"
#property strict

#ifndef MQLARTICLES_UTILS_SORT_BASE_SORT_MQH
#define MQLARTICLES_UTILS_SORT_BASE_SORT_MQH

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
#define MQLARTICLES_INSERTION_SORT_TRSHOLD (16)


//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
class CTsnSort
 {
private:
  //---
  template<typename TValue, typename TBase>
  static void        InternalSort(TValue& arr[], int lo, int hi, int depthLimit);
  template<typename TValue, typename TBase>
  static int         partition(TValue &arr[], int lo, int hi, TValue& pivot);
  template<typename TValue, typename TBase>
  static void        InsertionSort(TValue &arr[], int lo, int hi);
  template<typename TValue, typename TBase>
  static void        HeapSort(TValue &arr[], int lo, int hi);
  template<typename TValue, typename TBase>
  static void        Heapify(TValue &arr[], int parent, int heap_size, int lo);
  template<typename TValue, typename TBase>
  static void        Median3(TValue &arr[], int lo, int hi, TValue& pivot);
  template<typename TValue, typename TBase>
  static void        Sort3(TValue &xs[], int a, int b, int c);
  template<typename TValue, typename TBase>
  static void        Sort2(TValue &xs[], int a, int b);

public:
                     CTsnSort(void) {}
                    ~CTsnSort(void) {}

  //---
  template<typename TValue, typename TBase>
  static void        Sort(TValue& arr[], int lo, int hi);
 };

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
template<typename TValue, typename TBase>
static void CTsnSort::Sort(TValue& arr[], int lo, int hi)
 {
  const int size = hi - lo + 1;
  if(size < 2)
    return;
  const int depthLimit = int(MathFloor(MathLog(size) / M_LN2)) << 1;
  InternalSort<TValue, TBase>(arr, lo, hi, depthLimit);
 }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
template<typename TValue, typename TBase>
static void CTsnSort::InternalSort(TValue& arr[], int lo, int hi, int depthLimit)
 {
  while(lo < hi)
   {
    const int partitionSize = (hi - lo) + 1;
    //--- Insertion sort is faster for small partitions.
    if(partitionSize <= MQLARTICLES_INSERTION_SORT_TRSHOLD)
     {
      InsertionSort<TValue, TBase>(arr, lo, hi);
      return;
     }
    //--- If recursion depth exceeds limit, switch to heapsort to guarantee O(n log n).
    if(--depthLimit == 0)
     {
      HeapSort<TValue, TBase>(arr, lo, hi);
      return;
     }

    //--- Pick pivot as the median-of-three.
    TValue pivot;
    Median3<TValue, TBase>(arr, lo, hi, pivot);

    //--- Hoare’s partitioning scheme.
    const int p = partition<TValue, TBase>(arr, lo, hi, pivot);
    const int leftSize  = p - lo;
    const int rightSize = hi - p + 1;

    //--- Recurse into the smaller partition and process the larger one
    //--- iteratively. This guarantees O(log n) recursion depth.
    if(leftSize < rightSize)
     {
      InternalSort<TValue, TBase>(arr, lo, p - 1, depthLimit);
      lo = p;
     }
    else
     {
      InternalSort<TValue, TBase>(arr, p, hi, depthLimit);
      hi = p - 1;
     }
   }
 }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
template<typename TValue, typename TBase>
static int CTsnSort::partition(TValue &arr[], int lo, int hi, TValue& pivot)
 {
  while(lo <= hi)
   {
    while(TBase::Less(arr[lo], pivot))
      lo++;
    while(TBase::Less(pivot, arr[hi]))
      hi--;
    if(lo > hi)
      break;
    TBase::Swap(arr[lo++], arr[hi--]);
   }
  return lo;
 }
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
template<typename TValue, typename TBase>
static void CTsnSort::InsertionSort(TValue &arr[], int lo, int hi)
 {
  for(int i = lo + 1; i <= hi; i++)
   {
    if(TBase::Less(arr[i], arr[i - 1]))
     {
      TValue curr = arr[i];
      arr[i] = arr[i - 1];
      int j = i;
      while(--j > lo && TBase::Less(curr, arr[j - 1]))
        arr[j] = arr[j - 1];
      arr[j] = curr;
     }
   }
 }
//+------------------------------------------------------------------+
//| Heap Sort                                                        |
//+------------------------------------------------------------------+
template<typename TValue, typename TBase>
static void CTsnSort::HeapSort(TValue &arr[], int lo, int hi)
 {
  const int size = hi - lo + 1;
  for(int i = (size >> 1) - 1; i >= 0; i--)
   {
    Heapify<TValue, TBase>(arr, i, size, lo);
   }
  for(int i = size - 1; i > 0; i--)
   {
    TBase::Swap(arr[lo], arr[lo + i]);
    Heapify<TValue, TBase>(arr, 0, i, lo);
   }
 }
//+------------------------------------------------------------------+
//| Rebuilds the heap.                                               |
//+------------------------------------------------------------------+
template<typename TValue, typename TBase>
static void CTsnSort::Heapify(TValue &arr[], int parent, int heap_size, int lo)
 {
  TValue temp = arr[lo + parent];
  int child = (parent << 1) + 1;
  while(child < heap_size)
   {
    //---
    if(child + 1 < heap_size && TBase::Less(arr[lo + child], arr[lo + child + 1]))
      child++;
    if(!TBase::Less(temp, arr[lo + child]))
      break;

    //---
    arr[lo + parent] = arr[lo + child];
    parent = child;
    child = (parent << 1) + 1;
   }
  arr[lo + parent] = temp;
 }
//+------------------------------------------------------------------+
//| Get the median of three array elements.                          |
//+------------------------------------------------------------------+
template<typename TValue, typename TBase>
static void CTsnSort::Median3(TValue &arr[], int lo, int hi, TValue& pivot)
 {
  const int mid = lo + ((hi - lo) >> 1);
  Sort3<TValue, TBase>(arr, lo, mid, hi);
  pivot = arr[mid];
 }
//+------------------------------------------------------------------+
//| Sorts the elements a, b and c using comparison function less.    |
//+------------------------------------------------------------------+
template<typename TValue, typename TBase>
static void CTsnSort::Sort3(TValue &xs[], int a, int b, int c)
 {
  Sort2<TValue, TBase>(xs, a, b);
  Sort2<TValue, TBase>(xs, b, c);
  Sort2<TValue, TBase>(xs, a, b);
 }
//+------------------------------------------------------------------+
//| Sorts the elements a and b using comparison function less.       |
//+------------------------------------------------------------------+
template<typename TValue, typename TBase>
static void CTsnSort::Sort2(TValue &xs[], int a, int b)
 {
  if(TBase::Less(xs[b], xs[a]))
    TBase::Swap(xs[a], xs[b]);
 }
//+------------------------------------------------------------------+
#endif // MQLARTICLES_UTILS_SORT_BASE_SORT_MQH