If you would like, you could post a copy of your code, that was causing overflows, as a comment to this answer, and I could have a look at it for you. However, an incorrectly implemented midpoint calculation might cause the function to infinitely recurse and result in a stack overflow. 'mid = low + floor((high-low)/2)' works just fine too (they are mathematically equivalent), but the technique described in the article tends to be more intuitive for most people.Īs far as overflow issues go, you would exceed the largest possible array size (4294967295) long, long before the calculation described in the article would lose precision or have a numeric overflow (the largest int you can represent in javaScript is 9007199254740991 ). I suspect you made an error when you tried to implement the technique described. In fact, it is a fairly standard technique. It's unfortunate that you had problems with the challenge, but the technique describe in the article is not incorrect. The 1st copy of the function will return (and vanish). The Merge Above Together step will finish. The 2nd copy of the function will return (and vanish). The 1st copy of the function will move on to the next line. The 2nd copy of the function will move on to the next line. The 3rd copy of the function will return (and vanish). The call to MergeSort() will then generate a 3rd copy of the function The call to MergeSort() will then generate a 2nd copy of the function The 1st copy of the function will be made which looks like this: I'll denote each step that each version of the function is executing with a >. For MergeSort on arrays with = 2 elements the function is:

It is probably best illustrated with an example. So, if the currently executing copy of the MergeSort function was called by another copy of the MergeSort function to sort the calling functions left subarray, then after the currently executing version finishes, the version that called it will then move on to its next step, which is to call MergeSort to sort its right subarray.

When one function returns the function that called it continues to execute. When you use recursion, there may be several copies of a function, all at different stages in their execution.

Merge sorty