//+------------------------------------------------------------------+
//|                                                    RadixSort.mqh |
//|                                        Copyright © 2026, Amr Ali |
//|                             https://www.mql5.com/en/users/amrali |
//+------------------------------------------------------------------+
#property copyright "Copyright © 2026, Amr Ali"
#property link      "https://www.mql5.com/en/users/amrali"
#property version   "1.50"
#property description "Ultra-fast sorting for numeric arrays of any dimension."

#ifdef __MQL4__
#property strict
#endif

#ifndef RADIX_SORT_UNIQUE_HEADER_ID_H
#define RADIX_SORT_UNIQUE_HEADER_ID_H

//+------------------------------------------------------------------+
//| RadixSort                                                        |
//+------------------------------------------------------------------+
//| Sorts the values in the first dimension of a multidimensional    |
//| numeric array in the ascending order.                            |
//|                                                                  |
//| Arguments:                                                       |
//| array[]                                                          |
//|   [in][out] : Numeric array for sorting.                         |
//| descending                                                       |
//|   [in]      : false for ascending order (default), true for      |
//|               descending order.                                  |
//|                                                                  |
//| Return value: true if successful, otherwise false.               |
//|                                                                  |
//| Note:                                                            |
//|   An array is always sorted in the ascending order irrespective  |
//|   of the AS_SERIES flag value.                                   |
//|                                                                  |
//|   The function accepts any-dimensional arrays of simple type     |
//|   (char, uchar, short, ushort, int, uint, long, ulong, bool,     |
//|   color, datetime, float, double) as a parameter.  However,      |
//|   sorting is always applied to the first (zero) dimension.       |
//|                                                                  |
//| Performance:                                                     |
//|   This is a highly-optimized implementation of LSD RadixSort     |
//|   in MQL using radix-256 (8-bit digits). This could be useful    |
//|   for sorting huge numeric arrays with millions of numbers.      |
//|   It is at least 3-10 times faster than built-in ArraySort().    |
//|                                                                  |
//| IEEE-754 floating-point ordering:                                |
//|   Floating-point values are sorted by transforming their raw     |
//|   IEEE-754 bit representation into an order-preserving integer   |
//|   key. This produces the correct numerical ordering for all      |
//|   finite values without performing floating-point comparisons.   |
//|   Special values follow their IEEE-754 bit ordering: negative    |
//|   NaNs precede -infinity, positive NaNs follow +infinity, and    |
//|   -0.0 sorts before +0.0.                                        |
//+------------------------------------------------------------------+
template<typename T>
bool RadixSort(T &arr[], const bool descending = false)
  {
   const int n = ArraySize(arr);
//--- match the behavior of the built-in ArraySort():
//--- empty array -> false, single-element -> true.
   if(n < 2)
      return(n == 1);
//--- fall back to ArraySort() for a small array
   if(n < 128)
      return(ArraySort(arr) &&
         (!descending || ArrayReverse(arr)));
//--- temporary array to hold the sorted numbers
   T temp[];
   if(ArrayResize(temp, n) != n)
      return(false);
//--- frequency histogram of the i-th byte
   int counts[sizeof(T)][256];
//--- reset counts array
   ZeroMemory(counts);
//--- compute frequency histograms of the i-th byte
   for(int i = 0; i < n; i++)
     {
      const T ai = arr[i];
      for(uchar col = 0; col < sizeof(T); col++)
        {
         uchar key = extract_key(ai, (uchar)(col << 3));
         ++counts[col][key];
        }
     }
//--- checks whether the array is dynamic, in order to utilize ArraySwap() optimization on MT5.
   const bool dynamic = ArrayIsDynamic(arr);

//--- sort the array elements one byte at a time in LSD order (right-most byte first)
   for(uchar col = 0; col < sizeof(T); col++)
     {
      const uchar shift = col << 3;

      //--- determine if any columns can be skipped
      //--- for each digit, check if all the elements are in the same bucket.
      //--- If so, we can skip the whole digit. Instead of checking all the buckets,
      //--- we pick first key and check whether the bucket contains all the elements.
      if(counts[col][extract_key(arr[0], shift)] == n)
        {
         continue;
        }
      //--- transform counts to offset (ranks)
      int offset = 0;
      for(int i = 0; i < 256; i++)
        {
         int old_count = counts[col][i];
         counts[col][i] = offset;
         offset += old_count;
        }
      //--- gather forwards in temp (stable sort, elements ordered by i-th byte)
      for(int i = 0; i < n; i++)
        {
         uchar key = extract_key(arr[i], shift);
         temp[counts[col][key]++] = arr[i];
        }
      //--- copy back from temp to arr
      CopyOrSwap(arr, temp, dynamic);
     }
//---
   if(descending)
      return(ArrayReverse(arr));
//---
   return(true);
  }
//+------------------------------------------------------------------+
//| RadixSort                                                        |
//+------------------------------------------------------------------+
//| Sorts the values in the first dimension of a multidimensional    |
//| numeric array in the ascending order.                            |
//|                                                                  |
//| Function overload for two-dimensional numeric arrays.            |
//|                                                                  |
//| Arguments:                                                       |
//| array[]                                                          |
//|   [in][out] : Numeric array for sorting.                         |
//| descending                                                       |
//|   [in]      : false for ascending order (default), true for      |
//|               descending order.                                  |
//|                                                                  |
//| Return value: true if successful, otherwise false.               |
//|                                                                  |
//| Remark:                                                          |
//| This is a stable sort: rows with equal first-column values       |
//| retain their original relative order.                            |
//+------------------------------------------------------------------+
template<typename T>
bool RadixSort(T &arr[][], const bool descending = false)
  {
   const int n = ArraySize(arr);
   const int na = ArrayRange(arr, 0);
   const int nb = ArrayRange(arr, 1);
//--- match the behavior of the built-in ArraySort():
//--- empty array -> false, single-element -> true.
   if(na < 2)
      return(na == 1);
//--- fall back to ArraySort() for a small array
   if(na < 128)
      return(ArraySort(arr) &&
         (!descending || ArrayReverse(arr)));
//--- allocate temporary buffer to hold numbers from the first column
   T first_col[];
   if(ArrayResize(first_col, na) != na)
      return(false);
   for(int i = 0; i < na; i++)
      first_col[i] = arr[i][0];
//--- calculate order of numbers in the first dimension
   int indices[];
   if(!RadixSortIndices(first_col, indices))
      return(false);
//--- flatten the multidimensional numeric array into a properly-sized buffer
   T flat[];
   if(ArrayResize(flat, n) != n)
      return(false);
   if(ArrayCopy(flat, arr) != n)
      return(false);
//--- sort the flattened multidimensional array using the sorted indices.
   for(int i = 0; i < na; i++)
     {
      const int index = indices[i];
      for(int j = 0; j < nb; j++)
         arr[i][j] = flat[nb * index + j];
     }
//---
   if(descending)
      return(ArrayReverse(arr));
//---
   return(true);
  }
//+------------------------------------------------------------------+
//| RadixSort                                                        |
//+------------------------------------------------------------------+
//| Sorts the values in the first dimension of a multidimensional    |
//| numeric array in the ascending order.                            |
//|                                                                  |
//| Function overload for three-dimensional numeric arrays.          |
//|                                                                  |
//| Arguments:                                                       |
//| array[]                                                          |
//|   [in][out] : Numeric array for sorting.                         |
//| descending                                                       |
//|   [in]      : false for ascending order (default), true for      |
//|               descending order.                                  |
//|                                                                  |
//| Return value: true if successful, otherwise false.               |
//|                                                                  |
//| Remark:                                                          |
//| This is a stable sort: rows with equal first-column values       |
//| retain their original relative order.                            |
//+------------------------------------------------------------------+
template<typename T>
bool RadixSort(T &arr[][][], const bool descending = false)
  {
   const int n = ArraySize(arr);
   const int na = ArrayRange(arr, 0);
   const int nb = ArrayRange(arr, 1);
   const int nc = ArrayRange(arr, 2);
//--- match the behavior of the built-in ArraySort():
//--- empty array -> false, single-element -> true.
   if(na < 2)
      return(na == 1);
//--- fall back to ArraySort() for a small array
   if(na < 128)
      return(ArraySort(arr) &&
         (!descending || ArrayReverse(arr)));
//--- allocate temporary buffer to hold numbers from the first column
   T first_col[];
   if(ArrayResize(first_col, na) != na)
      return(false);
   for(int i = 0; i < na; i++)
      first_col[i] = arr[i][0][0];
//--- calculate order of numbers in the first dimension
   int indices[];
   if(!RadixSortIndices(first_col, indices))
      return(false);
//--- flatten the multidimensional numeric array into a properly-sized buffer
   T flat[];
   if(ArrayResize(flat, n) != n)
      return(false);
   if(ArrayCopy(flat, arr) != n)
      return(false);
//--- sort the flattened multidimensional array using the sorted indices.
   for(int i = 0; i < na; i++)
     {
      const int index = indices[i];
      for(int j = 0; j < nb; j++)
         for(int k = 0; k < nc; k++)
            arr[i][j][k] = flat[nc * (nb * index + j) + k];
     }
//---
   if(descending)
      return(ArrayReverse(arr));
//---
   return(true);
  }
//+------------------------------------------------------------------+
//| RadixSort                                                        |
//+------------------------------------------------------------------+
//| Sorts the values in the first dimension of a multidimensional    |
//| numeric array in the ascending order.                            |
//|                                                                  |
//| Function overload for four-dimensional numeric arrays.           |
//|                                                                  |
//| Arguments:                                                       |
//| array[]                                                          |
//|   [in][out] : Numeric array for sorting.                         |
//| descending                                                       |
//|   [in]      : false for ascending order (default), true for      |
//|               descending order.                                  |
//|                                                                  |
//| Return value: true if successful, otherwise false.               |
//|                                                                  |
//| Remark:                                                          |
//| This is a stable sort: rows with equal first-column values       |
//| retain their original relative order.                            |
//+------------------------------------------------------------------+
template<typename T>
bool RadixSort(T &arr[][][][], const bool descending = false)
  {
   const int n = ArraySize(arr);
   const int na = ArrayRange(arr, 0);
   const int nb = ArrayRange(arr, 1);
   const int nc = ArrayRange(arr, 2);
   const int nd = ArrayRange(arr, 3);
//--- match the behavior of the built-in ArraySort():
//--- empty array -> false, single-element -> true.
   if(na < 2)
      return(na == 1);
//--- fall back to ArraySort() for a small array
   if(na < 128)
      return(ArraySort(arr) &&
         (!descending || ArrayReverse(arr)));
//--- allocate temporary buffer to hold numbers from the first column
   T first_col[];
   if(ArrayResize(first_col, na) != na)
      return(false);
   for(int i = 0; i < na; i++)
      first_col[i] = arr[i][0][0][0];
//--- calculate order of numbers in the first dimension
   int indices[];
   if(!RadixSortIndices(first_col, indices))
      return(false);
//--- flatten the multidimensional numeric array into a properly-sized buffer
   T flat[];
   if(ArrayResize(flat, n) != n)
      return(false);
   if(ArrayCopy(flat, arr) != n)
      return(false);
//--- sort the flattened multidimensional array using the sorted indices.
   for(int i = 0; i < na; i++)
     {
      const int index = indices[i];
      for(int j = 0; j < nb; j++)
         for(int k = 0; k < nc; k++)
            for(int l = 0; l < nd; l++)
               arr[i][j][k][l] = flat[nd * (nc * (nb * index + j) + k) + l];
     }
//---
   if(descending)
      return(ArrayReverse(arr));
//---
   return(true);
  }
//+------------------------------------------------------------------+
//| RadixSortIndices                                                 |
//+------------------------------------------------------------------+
//| Populate an array of indices[] in the order that would sort      |
//| the values of a numeric array[] in the ascending order.          |
//|                                                                  |
//| Arguments:                                                       |
//| array[]     : Array with numeric values to sort                  |
//| indices[]   : Array for sorted indices                           |
//| descending  : false for ascending order (default), true for      |
//|               descending order.                                  |
//|                                                                  |
//| Return value: true if successful, otherwise false.               |
//+------------------------------------------------------------------+
template<typename T>
bool RadixSortIndices(const T &arr[], int &indices[], const bool descending = false)
  {
   const int n = ArraySize(arr);
//--- prepare array to hold the indices of the numbers
   if(ArrayResize(indices, n) != n)
      return(false);
   for(int i = 0; i < n; i++)
      indices[i] = i;
//--- allocate temporary buffer to hold the numbers
   T temp[];
   if(ArrayCopy(temp, arr) != n)
      return(false);
//--- calculate order of numbers in the ascending order
   if(!ParallelRadixSort(temp, indices, descending))
      return(false);
//---
   return(true);
  }
//+------------------------------------------------------------------+
//| ParallelRadixSort                                                |
//+------------------------------------------------------------------+
//| The function sorts array[] and items[] simultaneously using      |
//| the RadixSort algorithm. The items[] array (e.g. structs or      |
//| other data) is reordered according to the ascending numeric      |
//| values in array[].                                               |
//|                                                                  |
//| Arguments:                                                       |
//| array[]     : Array with numeric keys to sort                    |
//| items[]     : Array of items (e.g. structs) to sort by keys      |
//| descending  : false for ascending order (default), true for      |
//|               descending order.                                  |
//|                                                                  |
//| Return value: true if successful, otherwise false.               |
//+------------------------------------------------------------------+
template<typename T,typename TItem>
bool ParallelRadixSort(T &arr[], TItem &items[], const bool descending = false)
  {
   const int n = ArraySize(arr);
//--- match the behavior of the built-in ArraySort():
//--- empty array -> false, single-element -> true.
   if(n < 2)
      return(n == 1);
   if(ArraySize(items) != n)
      return(false);
//--- temporary array to hold the sorted numbers (keys)
   T temp[];
   if(ArrayResize(temp, n) != n)
      return(false);
//--- temporary array to hold the sorted items
   TItem items2[];
   if(ArrayResize(items2, n) != n)
      return(false);
//--- frequency histogram of the i-th byte
   int counts[sizeof(T)][256];
//--- reset counts array
   ZeroMemory(counts);
//--- compute frequency histograms of the i-th byte
   for(int i = 0; i < n; i++)
     {
      const T ai = arr[i];
      for(uchar col = 0; col < sizeof(T); col++)
        {
         uchar key = extract_key(ai, (uchar)(col << 3));
         ++counts[col][key];
        }
     }
//--- checks whether the arrays are dynamic, in order to utilize ArraySwap() optimization on MT5.
   const bool dynamic_arr   = ArrayIsDynamic(arr);
   const bool dynamic_items = ArrayIsDynamic(items);

//--- sort the array elements one byte at a time in LSD order (right-most byte first)
   for(uchar col = 0; col < sizeof(T); col++)
     {
      const uchar shift = col << 3;

      //--- determine if any columns can be skipped
      //--- for each digit, check if all the elements are in the same bucket.
      //--- If so, we can skip the whole digit. Instead of checking all the buckets,
      //--- we pick first key and check whether the bucket contains all the elements.
      if(counts[col][extract_key(arr[0], shift)] == n)
        {
         continue;
        }
      //--- transform counts to offset (ranks)
      int offset = 0;
      for(int i = 0; i < 256; i++)
        {
         int old_count = counts[col][i];
         counts[col][i] = offset;
         offset += old_count;
        }
      //--- gather forwards in temp (stable sort, elements ordered by i-th byte)
      for(int i = 0; i < n; i++)
        {
         uchar key = extract_key(arr[i], shift);
         offset = counts[col][key]++;
         temp[offset] = arr[i];
         items2[offset] = items[i];
        }
      //--- copy back from temp to arr
      CopyOrSwap(arr, temp, dynamic_arr);
      CopyOrSwap(items, items2, dynamic_items);
     }
//---
   if(descending)
     {
      return(ArrayReverse(arr)
         && ArrayReverse(items));
     }
//---
   return(true);
  }
//+------------------------------------------------------------------+
//| Copies or swaps the contents of two arrays.                      |
//|                                                                  |
//| Used internally by RadixSort() and ParallelRadixSort() to        |
//| reduce memory copying and improve performance. This helper       |
//| uses ArraySwap() for dynamic arrays on MQL5.                     |
//+------------------------------------------------------------------+
template<typename T>
void CopyOrSwap(T &dst[], T &src[], const bool is_dynamic)
  {
#ifdef __MQL5__
   if(is_dynamic)
      ArraySwap(dst, src);
   else
      ArrayCopy(dst, src);
#else
   ArrayCopy(dst, src);
#endif
  }
//+------------------------------------------------------------------+
//| Returns an integer key for "signed" primitive types.             |
//+------------------------------------------------------------------+
// https://github.com/eloj/radix-sorting#-key-derivation
// http://stereopsis.com/radix.html
// https://stackoverflow.com/a/42304235/4208440
// https://github.com/skarupke/ska_sort/blob/master/ska_sort.hpp
// https://github.com/JakubValtar/radsort/blob/master/src/scalar.rs
uchar extract_key(const char value, const uchar shift)
  {
   return (uchar)((value ^ 0x80) >> shift);
  }
uchar extract_key(const short value, const uchar shift)
  {
   return (uchar)((value ^ 0x8000) >> shift);
  }
uchar extract_key(const int value, const uchar shift)
  {
   return (uchar)((value ^ 0x80000000) >> shift);
  }
uchar extract_key(const long value, const uchar shift)
  {
   return (uchar)((value ^ 0x8000000000000000) >> shift);
  }
//+------------------------------------------------------------------+
//| Returns an integer key for float.                                |
//|                                                                  |
//| flip a float for sorting                                         |
//|  finds SIGN of fp number.                                        |
//|  if it's 1 (negative float), it flips all bits                   |
//|  if it's 0 (positive float), it flips the sign only              |
//|                                                                  |
//| The IEEE-754 bit pattern is transformed into a monotonically     |
//| increasing unsigned integer key while preserving the total order |
//| of all finite floating-point values.                             |
//|                                                                  |
//|   - Negative values sort before positive values.                 |
//|   - -0.0 sorts before +0.0.                                      |
//|   - NaNs are ordered by their raw bit patterns.                  |
//|   - Positive and negative infinities are ordered naturally.      |
//+------------------------------------------------------------------+
uchar extract_key(const float value, const uchar shift)
  {
   union _f { float value; uint bits; } f;
   f.value = value;

//--- extend the sign bit to the whole width with arithmetic
//--- right shift to get a flip mask 0xffffffff or 0x80000000
   return (uchar)((f.bits ^ (((int)f.bits >> 31) | 0x80000000)) >> shift);
  }
//+------------------------------------------------------------------+
//| Returns an integer key for double.                               |
//+------------------------------------------------------------------+
uchar extract_key(const double value, const uchar shift)
  {
   union _d { double value; ulong bits; } d;
   d.value = value;

//--- extend the sign bit to the whole width with arithmetic
//--- right shift to get a flip mask 0xffffffff or 0x80000000
   return (uchar)((d.bits ^ (((long)d.bits >> 63) | 0x8000000000000000)) >> shift);
  }
//+------------------------------------------------------------------+
//| Returns an integer key for other "unsigned" primitive types.     |
//| uchar, ushort, uint, ulong, bool, color, datetime.               |
//+------------------------------------------------------------------+
template<typename T>
uchar extract_key(const T value, const uchar shift)
  {
   return (uchar)(value >> shift);
  }
//+------------------------------------------------------------------+

#endif // #ifndef RADIX_SORT_UNIQUE_HEADER_ID_H