Radix sort (fastest numerical sort) - MetaTrader 5 library | MT5 EA download - MetaTrader 5 resources

Radix sort sorts numeric data (integers or floating point numbers) by considering a sequence of numbers, where they are sorted bit by bit from the least significant digit position to the most significant digit position.

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

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

This is a highly optimized implementation of LSD RadixSort in MQL using base 256 (8 bits). This is useful for sorting large arrays with millions of numbers.

This implementation is based on Pierre Terdiman's radix sort, published in http://codercorner.com/RadixSortRevisited.htm , with some optimizations posted by Michael Herf at http://stereopsis.com/radix.html By Eddy LO Jansson https://github.com/eloj/radix-sorting .

This function is at least 3-10 times faster Than MQL built-in arraysort() Function.

This function accepts any dimensional array of simple types (char, uchar, short, ushort, int, uint, long, ulong, bool, color, datetime, float, double) as parameters. However, sorting is always applied to the first (zero) dimension.

Regardless of the value of the AS_SERIES flag, the array is always sorted in ascending order.

Note that if the array contains fewer than a certain threshold (currently 128), the algorithm will fall back to ArraySort().

Radix sort should be the default for sorting numeric data because it operates on O(n*k) time. C comparison-based sorting algorithms (such as quick sort, merge sort, and heap sort) run in O(n * log n) time. Therefore, radix sort is relatively faster the larger the array size. The disadvantage of radix sort is that it requires more memory (temporary array) to do its job.

//+------------------------------------------------------------------+
//| RadixSort |
//+------------------------------------------------------------------+
//|Sort the values ​​in the first dimension of the multidimensional |
//|An array of values ​​sorted in ascending order.                            |
//| |
//|Parameters: |
//|Array[] |
//| [in][out] : Array of numbers used for sorting.                        |
//| |
//|Return value: Returns true if successful, otherwise returns false.              |
//| |
//|Note: |
//| Arrays are always sorted in ascending order regardless of |
//| AS_SERIES flag value.                                  |
//| |
//| This function accepts an arbitrary dimensional array of simple types |
//| (char, uchar, short, ushort, int, uint, long, ulong, bool, |
//| color, datetime, float, double) as parameters.  However, |
//| Sorting is always applied to the first (zero) dimension.      |
//| |
//|Performance: |
//| This is a highly optimized implementation of LSD RadixSort | |
//| Use base 256 (8 bits) in MQL. This might be useful for |
//| Sort huge numeric arrays containing millions of numbers.          |
//| It is at least 3-10 times faster than the built-in ArraySort().    |
//+------------------------------------------------------------------+
Template < type name > Boolean radix sort (T &arr[]); //+----------------------------------------------------------------------------------+
//| RadixSort |
//+------------------------------------------------------------------+
//|Sort the values ​​in the first dimension of the multidimensional |
//|An array of values ​​sorted in ascending order.                            |
//| |
//|Function overloading for high-dimensional numerical arrays.        |
//| |
//|Parameters: |
//|Array[] |
//| [in][out] : Array of numbers used for sorting.                        |
//| |
//|Return value: Returns true if successful, otherwise returns false.              |
//+------------------------------------------------------------------+
// Sort the two-dimensional numeric array.
Template < type name > Boolean value RadixSort(T &arr[][]); // Sort the three-dimensional numerical array.
Template < type name > Boolean value RadixSort(T &arr[][][]); // Sort the four-dimensional numerical array.
Template < type name > Boolean value RadixSort(T &arr[][][][]); //+----------------------------------------------------------------------------------+
//| RadixSortIndices |
//+------------------------------------------------------------------+
//|Fill the index[] array in sorted order |//|The values ​​of numeric array[] are arranged in ascending order.          | //| | //|Parameters: | //| array[]: numeric array to be sorted | //| Index[]: array of sorted indexes | //| | //|Return value: Returns true if successful, otherwise returns false.              | //+------------------------------------------------------------------+ Template < type name > Boolean radix sort index ( constant T&arr[], integer & index[]); //+------------------------------------------------------------------+ //| ParallelRadixSort | //+----------------------------------------------------------------+ //|This function uses | to sort array[] and items[] at the same time //| Radix sort algorithm. After sorting, the items[] array is sorted| //|Arranged in ascending order by the value of array[].        | //| | //|Parameters: | //| array[]: array sorted using numeric keys | //| items[]: array of items sorted according to keys | //| | //|Return value: Returns true if successful, otherwise returns false.              | //+------------------------------------------------------------------+ Template < type name ton, type name item> Boolean value ParallelRadixSort(T &arr[], TItem &items[]);

Here is a benchmark script demonstrating the speed advantage of RadixSort() over MQL's ArraySort():

 //+------------------------------------------------------------------+
//| RadixSort_benchmark.mq5 |
//| Copyright © 2018, Eminem Ali |
//| https://www.mql5.com/en/users/amrali |
//+------------------------------------------------------------------+
#include "radixsort.mqh"

#define size 10 * 1000 * 1000 // 10 million
Integer arr1[size]; integer arr2[size]; //+----------------------------------------------------------------------------------+
//| |
//+------------------------------------------------------------------+
blank start ()
  { //--- Prepare an unsorted array. for ( integer i = 0 ; i < size; i++)
    {
      arr1[i] = math rand ();
      arr2[i] = arr1[i];
    } //--- ArraySort() benchmark. Unit t1= Get the number of ticks ();
arraysort (arr1);
Unit scale 1 = get number of scales () - t1; //--- RadixSort() benchmark. Unit t2= Get the number of ticks ();
  Radix sort(arr2);
Unit scale 2 = get the number of scales ()-t2; //--- display the result. printFormat ( "Sort %d integers:" , size);
Print format ( "ArraySort() -> %u milliseconds" , scale 1);
Print format ( "RadixSort() -> %u milliseconds" , scale 2);
Print format ( "Acceleration coefficient is %.1fx" , ( double ) scale 1/scale 2);
Print format ( "%s" , array comparison (arr1, arr2) ? "RadixSort: Invalid sort order." : "" );
  } //+------------------------------------------------------------------+

// Sample output:
/*
 Sort 10000000 integers:
 ArraySort() -> 953 milliseconds RadixSort() -> 62 milliseconds acceleration factor is 15.4 times */

To replace MQL's ArraySort() with RadixSort() in an old mq5 or mqh file, just add these two lines at the top of the file:

 #include "radixsort.mqh"
#Define array sort (a) radix sort(a)

Attachment download

📎radixsort.mqh (37.14 KB)

📎radixsort_benchmark.mq5 (3.23 KB)

📎 radixsort_validate_types.mq5 (8.19 KB)

Source: MQL5 #38763