Radix sort (The fastest numeric sort) - library for MetaTrader 5

Radix sort (The fastest numeric sort) – library MetaTrader 5

by

RadixSort Algorithm

RadixSort sorts numeric data (integers or float) by considering a string of numbers where digit by digit sort starting from least significant digit position to most significant digit position.

The algorithm is better explained on that Wikipedia page https://en.wikipedia.org/wiki/Radix_sort


Time Complexity and Performance

Radix sort has linear time complexity, it operates in O(n * k) time, where:

    n = the number of elements to sort
    k = the maximum element width (number of bytes) of the elements to sort

The algorithm iterates over k byte places in LSD (least significant digit) order; for each byte place, it iterates over all n elements to sort them by the k-th byte.

RadixSort Implementation in MQL

This is a highly-optimized implementation of LSD RadixSort in MQL using radix 256 (8-bits). This could be useful for sorting huge arrays with millions of numbers.

This implementation is based on radix sort by Pierre Terdiman, published at http://codercorner.com/RadixSortRevisited.htm, with select optimizations published by Michael Herf at http://stereopsis.com/radix.html and by Eddy L O Jansson at https://github.com/eloj/radix-sorting.

The function is at least 3-10 times faster than MQL’s built-in ArraySort() function. 

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. 

An array is always sorted in the ascending order irrespective of the AS_SERIES flag value.

Note that, the algorithm falls back to ArraySort() if the array contains less than some threshold of items (currently 128).

Radix sort should be the default for sorting numeric data as it operates in O(n * k) time. Comparison-based sorting algorithms (like quicksort, mergesort and heapsort) run in O(n * log n) time. Thus, Radix sort is comparatively faster, the larger the array size. The downside of radix sort is that it needs more memory (temporary array) to do its work.

 

//+------------------------------------------------------------------+
//| 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.                         |
//|                                                                  |
//| 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-bits). 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().    |
//+------------------------------------------------------------------+
template<typename T>
bool RadixSort(T &arr[]);


//+------------------------------------------------------------------+
//| RadixSort                                                        |
//+------------------------------------------------------------------+
//| Sorts the values in the first dimension of a multidimensional    |
//| numeric array in the ascending order.                            |
//|                                                                  |
//| Function overload for higher-dimensional numeric arrays.         |
//|                                                                  |
//| Arguments:                                                       |
//| array[]                                                          |
//|   [in][out] : Numeric array for sorting.                         |
//|                                                                  |
//| Return value: true if successful, otherwise false.               |
//+------------------------------------------------------------------+
// Sorts two-dimensional numeric arrays.
template<typename T>
bool RadixSort(T &arr[][]);


// Sorts three-dimensional numeric arrays.
template<typename T>
bool RadixSort(T &arr[][][]);

// Sorts four-dimensional numeric arrays.
template<typename T>
bool RadixSort(T &arr[][][][]);


//+------------------------------------------------------------------+
//| 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                           |
//|                                                                  |
//| Return value: true if successful, otherwise false.               |
//+------------------------------------------------------------------+
template<typename T>
bool RadixSortIndices(const T &arr[], int &indices[]);


//+------------------------------------------------------------------+
//| ParallelRadixSort                                                |
//+------------------------------------------------------------------+
//| The function sorts array[] and items[] simultaneously using      |
//| RadixSort algorithm. After sorting the items[] array is sorted   |
//| by the numeric values of array[] in the ascending order.         |
//|                                                                  |
//| Arguments:                                                       |
//| array[]     : Array with numeric keys to sort                    |
//| items[]     : Array for items to sort based on keys              |
//|                                                                  |
//| Return value: true if successful, otherwise false.               |
//+------------------------------------------------------------------+
template<typename T,typename TItem>
bool ParallelRadixSort(T &arr[], TItem &items[]);

This is a benchmark script that demonstrates the speed advantage of RadixSort() over MQL’s ArraySort():

Alternative:  MartingailExpert - EA MetaTrader 5
//+------------------------------------------------------------------+
//|                                          RadixSort_benchmark.mq5 |
//|                                        Copyright © 2018, Amr Ali |
//|                             https://www.mql5.com/en/users/amrali |
//+------------------------------------------------------------------+
#include "RadixSort.mqh"

#define SIZE 10*1000*1000  // 10 millions
int     arr1[SIZE];
int     arr2[SIZE];
//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
void OnStart()
  {
//--- Prepare unsorted arrays.
   for(int i = 0; i < SIZE; i++)
     {
      arr1[i] = MathRand();
      arr2[i] = arr1[i];
     }

//--- ArraySort() benchmark.
   uint t1 = GetTickCount();
   ArraySort(arr1);
   uint ticks1 = GetTickCount() - t1;

//--- RadixSort() benchmark.
   uint t2 = GetTickCount();
   RadixSort(arr2);
   uint ticks2 = GetTickCount() - t2;

//--- Display results.
   PrintFormat("Sorting %d integers: ", SIZE);
   PrintFormat("ArraySort() -> %u millisec", ticks1);
   PrintFormat("RadixSort() -> %u millisec", ticks2);
   PrintFormat("Speed-up factor is %.1fx", (double)ticks1/ticks2);
   PrintFormat("%s", ArrayCompare(arr1, arr2) ? "RadixSort: invalid sort order.": "");
  }
//+------------------------------------------------------------------+

// sample output:
/*
 Sorting 10000000 integers:
 ArraySort() -> 953 millisec
 RadixSort() -> 62 millisec
 Speed-up factor is 15.4x
*/

To replace MQL’s ArraySort() by RadixSort() in your old mq5 or mqh files, just add these two lines at the top of the file:

Alternative:  Elder Auto Envelopes - indicator MetaTrader 5
#include "RadixSort.mqh"

#define ArraySort(a) RadixSort(a)

Radix sort (The fastest numeric sort) – library MetaTrader 5
📈 ROBOTFX MetaTrader Expert Advisors and Indicators to maximize profits and minimize the risks

Similar MetaTrader Trading Tools:

  • Introsort (Introspective sort) - library for MetaTrader 5
    Introsort (Introspective sort) - library MetaTrader 5     Introspective SortIntro or Introspective sort is a hybrid sorting algorithm that provide fast performance. It is a comparison based sorting…
  • gnome sort - array sorting algorithm - library for MetaTrader 5
    gnome sort - array sorting algorithm - library MetaTrader 5     //+------------------------------------------------------------------+ //|                                                    GnomeSort.mq5 | //|                                    2019-2021, dimitri pecheritsa | //|                                         mql5.com/en/users/dmipec | //|------------------------------------------------------------------| //|  c  | gnome sort                                                 | //|------------------------------------------------------------------| //| use | array…
  • insertion sort - array sorting algorithm - library for MetaTrader 5
    insertion sort - array sorting algorithm - library…     //+------------------------------------------------------------------+ //|                                                InsertionSort.mq5 | //|                                    2019-2021, dimitri pecheritsa | //|                                         mql5.com/en/users/dmipec | //|------------------------------------------------------------------| //| cls | insertion sort                                             | //|------------------------------------------------------------------| //| use…
  • selection sort - array sorting algorithm - library for MetaTrader 5
    selection sort - array sorting algorithm - library…     //+------------------------------------------------------------------+ //|                                                SelectionSort.mq5 | //|                                    2019-2021, dimitri pecheritsa | //|                                         mql5.com/en/users/dmipec | //+------------------------------------------------------------------+ //| selection sort - array sorting algorithm                         | //+------------------------------------------------------------------+…
  • shell sort - array sorting algorithm - library for MetaTrader 5
    shell sort - array sorting algorithm - library MetaTrader 5     //+------------------------------------------------------------------+ //|                                                    ShellSort.mq5 | //|                                    2019-2021, dimitri pecheritsa | //|                                         mql5.com/en/users/dmipec | //+------------------------------------------------------------------+ //+------------------------------------------------------------------+ //| shell sort - array sorting algorithm                             |…
  • heap sort - array sorting algorithm - library for MetaTrader 5
    heap sort - array sorting algorithm - library MetaTrader 5     //+------------------------------------------------------------------+ //|                                                     HeapSort.mq5 | //|                                  2019 - 2021, dimitri pecheritsa | //|                             https://www.mql5.com/en/users/dmipec | //+------------------------------------------------------------------+ //+------------------------------------------------------------------+ //| heap sort - array…
  • merge sort - a merging method comparison-based sorting algorithm - library for MetaTrader 5
    merge sort - a merging method comparison-based…     //+------------------------------------------------------------------+ //|                                                    MergeSort.mq5 | //|                                    2019-2020, dimitri pecheritsa | //|                                                 792112@gmail.com | //+------------------------------------------------------------------+ //   merge sort - a merging method comparison-based sorting…
  • quick sort - sorting algorithm - library for MetaTrader 5
    quick sort - sorting algorithm - library MetaTrader 5     //+------------------------------------------------------------------+ //|                                                    QuickSort.mq5 | //|                                    2019-2020, dimitri pecheritsa | //|                                                 792112@gmail.com | //+------------------------------------------------------------------+ // //   quick sort - sorting algorithm // //  …