Introsort (Introspective sort) using Function Pointers - library for MetaTrader 5

Introspective Sort

This is a revised version of the original Introsort library, now the Introsort() function accepts an optional function pointer to custom comparison function.

Intro or Introspective sort is a hybrid sorting algorithm that provide fast performance. It is a comparison based sorting algorithm based on three phases. It uses the quicksort sort along with heapsort and insertion-sort algorithms. 

Quick Sort
Quick sort is a divide and conquer algorithm which works by selecting a pivot element in the array, then partitions the other elements into two subarrays checking the condition whether the elements are greater or smaller. On average the quick sort alogirthm takes O(nlog(n)) time, with worst case complexity of O(n²).

Heap Sort
Heap sort algoirthm is a binary-heap based comparison based sorting method. It is an unstable sorting algorithm with worst case and average case time complexity of O(nlog(n)), and best case time complexity of O(n).

Insertion Sort
Insertion sort algorithm is a simple sorting method that builds the final sorted array one item at a time. It's time complexity for worst case and average case is O(n²) and best case is O(n).

Introsort algorithm combines the good parts of these three algorithms. It begins with quick sort, switching to heapsort when the recursion depth exceeds a level based on the number of elements begin sorted and switchs to insertion sort when the number of elements are less than some threshold value.

• If the partition size is such that there is a possibility to exceed the maximum depth limit then the Introsort switches to Heapsort.
• If the partition size is too small then Quicksort switches to Insertion Sort.
• If the partition size is under the limit and not too small, then it performs a simple quicksort.

Introsort has particularly good runtime behavior. It is one of the fastest comparison sorting, algorithms in use today, and is the usual implementation of the std::sort algorithm provided with the C++ STL, Microsoft .NET Framework Class Library, GNU Standard C++ library, and LLVM libc++ library.

//+------------------------------------------------------------------+
//| 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.
 */
template<typename T>
void Introsort(T &arr[]);

//+------------------------------------------------------------------+
//| 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);

Comparison function Less:

bool MyLessFunc(const MyStruct &x, const MyStruct &y)
  {
//--- sort by A (asc)
   if(x.A < y.A) return(true);
   if(x.A > y.A) return(false);

//--- if equal on A, sort by B (asc)
   if(x.B < y.B) return(true);
   if(x.B > y.B) return(false);

//--- if equal on B, sort by C (asc)
   if(x.C < y.C) return(true);
   if(x.C > y.C) return(false);

//--- all keys are equal
   return(false);
  }


// Define a pointer type to custom Less function.
typedef bool (*pLess)(const MyStruct &x, const MyStruct &y);


// Sort array of structures using custom Less function.
Introsort(structArray, (pLess)MyLessFunc);