Recursive Functions

New comment
 

I am trying to use Merge Sort to manually sort an array variable. The reason, I am not using the ArraySort() function is because I am going to edit the code so that I can sort a few other arrays based on the first array. However, I want to make sure the base algorithm was implemented properly.


This is where the problem lies, everything compiling properly except for the first recursive function call. The Error message that it gives me is: 'MergeSort' - expression of 'void' type is illegal. So I thought to myself, that mql5 has a problem with void recursive calls, so I did a new implementation where I return 1 (i.e changing the MergeSort to an integer returning function) and this gets rid of the error message.


What is the explanation for this, I am curious? I could not find anything in the documentation. Is there anything I could do to change the implementation MergeSort so you can do it with void functions? (Thanks In Advanced)


Void function implementation below (Error-Inducing): 

void MergeSort(double &arr[], int left, int right){
   if(left >= right){
      return; 
   }
   int mid = (left + right)/2;
   MergeSort(arr, left, mid);
   MergeSort(arr, mid + 1, right)/2;
   Merge(arr, left, mid, right);
}

void Merge(double &arr[], int left, int mid, int right){
   int size_of_left = mid - left + 1;
   int size_of_right = right - mid; 
   
   long left_arr[];
   long right_arr[];
   ArrayResize(left_arr, size_of_left);
   ArrayResize(right_arr, size_of_right);
   
   for (int i = 0; i < size_of_left; i++)
      left_arr[i] = arr[left + i];
   
   for (int j = 0; j < size_of_right; j++)
      right_arr[j] = arr[mid + 1 + j];
   
   int index_of_left_arr = 0;
   int index_of_right_arr = 0;
   int index_of_merged_arr = 0;
   
   while(index_of_left_arr < size_of_left && index_of_right_arr < size_of_right){
      if(left_arr[index_of_left_arr] < right_arr[index_of_right_arr]){
         arr[index_of_merged_arr] = left_arr[index_of_left_arr];
         index_of_left_arr += 1;
      }
      else{
         arr[index_of_merged_arr] = right_arr[index_of_right_arr];
         index_of_right_arr += 1;
      }
      index_of_merged_arr += 1;
   }
   
   while(index_of_left_arr < size_of_left){
      arr[index_of_merged_arr] = left_arr[index_of_left_arr];
      index_of_left_arr += 1;
      index_of_merged_arr += 1;
   }
   
   while(index_of_right_arr < size_of_right){
      arr[index_of_merged_arr] = right_arr[index_of_right_arr];
      index_of_right_arr += 1;
      index_of_merged_arr += 1;
   }
        
}
 
Division of outcome of MergeSort by 2 is illegal. void can not be divided by 2

MergeSort(arr, mid + 1, right) / 2;  

 
Amir Yacoby #:
Division of outcome of MergeSort by 2 is illegal. void can not be divided by 2

MergeSort(arr, mid + 1, right) / 2;  

So Blind, thank you!


Edit: If anyone was wondering, the body of Merge has a small error. index_of_merged_arr should be initialized to be left. 

 

Hi TraderTogami,

Here is my optimized version of merge sort. Its speed is comparable to quick sort, and it is faster than ArraySort().

//+------------------------------------------------------------------+
//| Merge Sort                                                       |
//+------------------------------------------------------------------+
/*
 * Sort the input array in-place in ascending order.
 * It is often te best choice for sorting a linked list / collections (stable).
 * It is efficient at handling slow-to-access sequential media.
 * Complexity: O(n log n) - Quasilinear time
 * Adaptive  : +
 * Stable    : yes
 *
 * Optimizations:
 *
 * 1. Eliminate the copy to the auxiliary array. (we can arrange the recursive calls
 *    such that the computation switches the roles of the input array and the auxiliary
 *    array at each level).
 * 2. Test whether subarray is already in order. With this change, the running time for
 *    any sorted subarray is linear.
 */
template<typename T>
void MergeSort(T &arr[])
  {
   MergeSort(arr, 0, ArraySize(arr) - 1);
  }

template<typename T>
void MergeSort(T &arr[], int lo, int hi)
  {
   T temp[];
//--- Create a copy of the original array. Switching between
//--- original array and its copy will allow to avoid
//--- additional array allocations and data copying.
   ArrayCopy(temp, arr);
   SplitMerge(arr, temp, lo, hi);
  }

template<typename T>
void SplitMerge(T &arr[], T &temp[], int lo, int hi)
  {
   if(lo >= hi)
      return;
   int mid = lo + (hi - lo) / 2;
   SplitMerge(temp, arr, lo, mid);
   SplitMerge(temp, arr, mid + 1, hi);
   Merge(arr, temp, lo, mid, hi);
  }

//--- Merge two sorted sub arrays src[lo..mid] and src[mid+1..hi] to dst[lo..hi]
template<typename T>
void Merge(T &dst[], T &src[], int lo, int mid, int hi)
  {
//--- Stop if already sorted.
//--- Is biggest element in first half <= smallest element in second half?
//--- Helps for nearly ordered lists (adaptive).
   if(mid + 1 < hi && src[mid] <= src[mid + 1])
     {
      ArrayCopy(dst, src, lo, lo, hi - lo + 1);
      return;
     }
   int i = lo, j = mid + 1;
   for(int k = lo; k <= hi; k++)
     {
      if(i > mid)
        {
         dst[k] = src[j++];
        }
      else if(j > hi)
        {
         dst[k] = src[i++];
        }
      else
        {
         dst[k] = ((src[i] < src[j]) ? src[i++] : src[j++]);
        }
     }
  }
New comment
Reason: