Maximum call stack size exceeded error with merge sort function

p5.js Coding Questions
1

Here is the function, it calls ‘Uncaught RangeError: Maximum call stack size exceeded’ when run, I’m not sure why this is happening. I’m thinking somewhere it’s getting caught in an infinite loop:

function mergeSort(vals) {
  if (vals.length > 1) {
    let mid = floor(vals.length / 2);
    let left = [];
    let right = [];
    
    for (let i = 0; i <= mid; i++) {
      left.push(vals[i]);
    }
    for (let i = mid+1; i < vals.length; i++) {
      right.push(vals[i]);
    }

    mergeSort(left);
    mergeSort(right);
    
    // Merge
    let i, j, k = 0;

    while (i < left.length && j < right.length) {
      if (left[i] < right[j]) {
        values[k] = left[i];
        i++;
      }
      else {
        values[k] = right[j];
        j++;
      }
      k++;
    }

    while (i < left.length) {
      values[k] = left[i];
      i++;
      k++;
    }

    while (j < right.length) {
      values[k] = right[j];
      j++;
      k++;
    }
  }
}
2

I haven’t run the code so just guessing (it would be helpful if you can provide the complete code with what array you are using etc so we can actually run it) - I see that in left you include mid. This is problematic if you think about inputting an array of 2 elements, both end up in left and nothing in right causing infinite recursion.

I think the guideline on this forum shows you some tips on debugging. In this case you can try to console.log(vals) to see what’s actually happening and also use simple examples (what if the array length is only 1, what if 2,…) to narrow down the problem.

1 Like
3

I fixed the case with the left including mid and it now runs but doesn’t do anything. Guess I’ll go from here thanks for the help!

4

Where is this variable values initialized?:

        values[k] = left[i];

EDIT (March 28, 2021):

Perhaps it is a global variable that is being used within the function, which means that the function is not self-contained. Consequently, we need to have the entire surrounding context of the function available to us in order to reproduce whatever problems you are having.

5

It’s a global variable containing the unsorted values.

6

Because the function receives the data via a parameter and also operates on that data via an external variable, it is difficult to keep track of what the function is doing.

EDIT (March 29, 2021):

@michaelberge, if you can provide us with that code, we would be in a better position to understand the relationship between the function and the data, and to diagnose the problem.