Program is still in infinite recursion

Question

I am trying to create a Merge Sort using Wolfram Mathematica, but I am still getting this recursion error and I have no idea, where I made a misstake. I rewrite this code from Java, where it works just fine, so I guess it is some special thing for Wolfram. Do you have any idea, what could be wrong with my code?

Thanks a lot!

Heer is my code:

mergeSort[x_, left_, right_] := 
 Module[{array = x, middle, n1, n2, L, R, i, j, k}, 
  If[left < right,
    middle = (left + right) / 2;
    
    mergeSort[array, left, middle];
    mergeSort[array, middle + 1, right];
    
    n1 = middle - left + 1;
    n2 = right - middle;
    
    L = {};
    R = {};
    
    For[i = 1, i < n1, ++i,
     L[[i]] = array[[left + 1]];
     ];
    For[j = 1, j < n2, ++j,
     R[[j]] = array[[middle + 1 + j]];
     ];
    
    i = 0;
    j = 0;
    k = left;
    
    While[i < n1 && j < n2,
     If[L[[i]] <= R[[j]],
      array[[k]] = L[[i]];
      i++;
      ,
      array[[k]] = R[[j]];
      j++;
      ];
     k++;
     ];
    
    While[i < n1, 
     array[[k]] = L[[i]];
     i++;
     k++;
     ];
    
    While[j < n2,
     array[[k]] = R[[j]];
     j++;
     k++;
     ];
    Return[array];
    ];
  ]

Here is my function call - mergeSort[{58, 3, 98}, 0, 3];

Answer 1

You have three main problems in your code.

1. The GfG code you are trying to adapt is passing the array arr by reference, so each recursion is operating on the same object. This doesn't ordinarily happen in Mathematica. I have added HoldFirst to pass array by reference. An alternative would be to simply leave array out of the function calls altogether and modify it directly as a global variable. E.g.

   mergeSort[left_, right_] := Module[{},
     If[left < right,
      middle = Floor[(left + right)/2];
      mergeSort[left, middle];
      mergeSort[middle + 1, right];
      ...
   

2. Where the GfG code does int m = (l + r) / 2 the result is rounded down. This needs to be done explicitly in Mathematica: middle = Floor[(left + right)/2]. Otherwise you get infinite recursion.

3. The GfG code uses zero-based arrays. Mathematica uses one-based lists, so code such as for (int i = 0; i < n1; ++i) can be changed to For[i = 1, i <= n1, ++i, ...

You also had a typo from this line in the GfG code: L[i] = arr[l + i], and finally you do not need to use Return in Mathematica to return values at the end of a function.

Attributes[mergeSort] = HoldFirst;

mergeSort[array_Symbol, left_Integer, right_Integer] :=
 Module[{middle, n1, n2, L, R, i, j, k},
  If[left < right,
   middle = Floor[(left + right)/2];

   mergeSort[array, left, middle];
   mergeSort[array, middle + 1, right];

   n1 = middle - left + 1;
   n2 = right - middle;

   L = ConstantArray[Null, n1];
   R = ConstantArray[Null, n2];

   For[i = 1, i <= n1, ++i,
    L[[i]] = array[[left + i - 1]];
    ];
   For[j = 1, j <= n2, ++j,
    R[[j]] = array[[middle + j]];
    ];

   i = 1;
   j = 1;
   k = left;

   While[i <= n1 && j <= n2,
    If[L[[i]] <= R[[j]],
     array[[k]] = L[[i]];
     i++;
     ,
     array[[k]] = R[[j]];
     j++;
     ];
    k++;
    ];

   While[i <= n1,
    array[[k]] = L[[i]];
    i++;
    k++;
    ];

   While[j <= n2,
    array[[k]] = R[[j]];
    j++;
    k++;
    ];
   array
   ]
  ]

array = {58, 3, 98};

mergeSort[array, 1, Length[array]]

{3, 58, 98}

Note this has changed the contents of array.

array

{3, 58, 98}

Alternative Version

A version much more in the Mathematica idiom is this, by Wellin, Gaylord & Kamin.

merge[lis_List, {}] := lis
merge[{}, lis_List] := lis

merge[{a_, ra___}, {b_, rb___}] :=
 If[a <= b,
  Join[{a}, merge[{b}, {ra, rb}]],
  Join[{b}, merge[{a, ra}, {rb}]]]

MergeSort[{}] := {}
MergeSort[{x_}] := {x}
MergeSort[lis_List] := Module[{div = Floor[Length[lis]/2]},
  merge[MergeSort[Take[lis, div]], MergeSort[Drop[lis, div]]]]

MergeSort[{58, 3, 98}]

{3, 58, 98}