Implementing merge sort in Javascript

Question

So I'm working on Khan Academy's Algorithms course, and am trying to implement a recursive merge sort in Javascript. Here is my code so far: ``` var mergeSort = function(array, p, r) { if(r>p) { var q = floor(r/2); mergeSort(array, p, q); mergeSort(array, q+1, r); merge(array, p, q, r); } }; ``` merge is a function provided by Khan Academy to merge the subarrays back together. It is giving me the error: 'Uncaught RangeError: Maximum call stack size exceeded'. EDIT: More details: I am fairly sure the error is in my code, there code is purposefully obfuscated and unreadable because the user needs to implement it themselves in a later challenge. Here is the code that actually calls the mergeSort function initially and declares the array: ``` var array = [14, 7, 3, 12, 9, 11, 6, 2]; mergeSort(array, 0, array.length-1); println("Array after sorting: " + array); Program.assertEqual(array, [2, 3, 6, 7, 9, 11, 12, 14]); ``` And here is the code for the merge function, although it is obfuscare…

Accepted Answer

`q` is supposed to be the half way point between `p` and `r`, but you've failed to take into account that the starting point (i.e. `p`) might not be `0` when you do this:

```
var q = floor(r/2);
```

You need to do something like:

```
var q = floor((r-p)/2) + p;
```

Although as @Oriol points out the middle point is actually exactly the same as the arithmetic mean and so the calculation can be simplified.

Implementing merge sort in Javascript

Solution

Problem