Question 1

Based on pseudocode
MergeSort(array A, int p, int r) {
if (p < r) { // we have at least 2 items
q = (p + r)/2
MergeSort(A, p, q) // sort A[p..q]
MergeSort(A, q+1, r) // sort A[q+1..r]
Merge(A, p, q, r) // merge everything together
}
}
I dont understand one thing, after the mergesort left right are done, the merge will be run. It is supposed to end there, but it it said that the control run back to the mergesort right to keep going on. Why is that happen while I dont see any code to do that after the merge? Please explain to me clearly, I am not so smart :(

Accepted Answer

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

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.
It is probably best illustrated with an example.

In the below example:
- For MergeSort on arrays with <2 elements the function is: Do Nothing
- For MergeSort on array with >= 2 elements the function is:
```
  MergSort(left subarray)
  MergeSort(right subarray)
  Merge Above Together
```
- I'll denote each step that each version of the function is executing with a >.

Suppose we call MergeSort on [4,3,2]

The 1st copy of the function will be made which looks like this:
```
>  MergeSort([4,3])
   MergeSort([2])
   Merge Above Together
```

The call to MergeSort([4,3]) will then generate a 2nd copy of the function 
(shown below the 1st copy)

```
>  MergeSort([4,3])
   MergeSort([2])
   Merge Above Together

>  MergeSort([4])
   MergeSort([3])
   Merge Above Together
```

The call to MergeSort([4]) will then generate a 3rd copy of the function 
(shown below the 2nd copy)

```
>  MergeSort([4,3])
   MergeSort([2])
   Merge Above Together

>  MergeSort([4])
   MergeSort([3])
   Merge Above Together

>  Do Nothing
```

The Do Nothing step will finish. The 3rd copy of the function will return (and vanish).
The 2nd copy of the function will move on to the next line.

```
>  MergeSort([4,3])
   MergeSort([2])
   Merge Above Together

MergeSort([4])
>  MergeSort([3])
   Merge Above Together
```

The call to MergeSort([3]) will then generate a 3rd copy of the function 
(shown below the 2nd copy)

```
>  MergeSort([4,3])
   MergeSort([2])
   Merge Above Together

MergeSort([4])
>  MergeSort([3])
   Merge Above Together

>  Do Nothing
```

The Do Nothing step will finish. The 3rd copy of the function will return (and vanish).
The 2nd copy of the function will move on to the next line.
```
>  MergeSort([4,3])
   MergeSort([2])
   Merge Above Together

MergeSort([4])
   MergeSort([3])
>  Merge Above Together
```

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.
```
   MergeSort([4,3])
>  MergeSort([2])
   Merge Above Together
```

The call to MergeSort([2]) will then generate a 2nd copy of the function 
(shown below the 1st copy) 
```
   MergeSort([4,3])
>  MergeSort([2])
   Merge Above Together

>  Do Nothing
```

The Do Nothing 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.

```
   MergeSort([4,3])
   MergeSort([2])
>  Merge Above Together
```
The Merge Above Together step will finish. The 1st copy of the function will return (and vanish).
The array should now be sorted.

Hope this makes sense

Question 2

I spent hours trying to figure out the challenge while I kept getting overflow issues. Hours later I found out that the above tutorial does not properly state the "Divide" portion.

Incorrect: "Divide by finding the number qq of the position midway between pp and rr. Do this step the same way we found the midpoint in binary search: add pp and rr, divide by 2, and round down."

I found the correct way to perform the "Divide" step by researching the code online. I came across a post with the code written in C, and the way to find "q" is completely different. Pay attention to the top portion of the code where it talks about the "mid" variable.

http://stackoverflow.com/questions/12030683/implementing-merge-sort-in-c#answer-12030723

I hope this post saves someone from the same headaches as I had to endure.

Accepted Answer

It's unfortunate that you had problems with the challenge, but the technique describe in the article is not incorrect. In fact, it is a fairly standard technique. I just checked it and it works for me. I suspect you made an error when you tried to implement the technique described.

'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.

As 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 ). However, an incorrectly implemented midpoint calculation might cause the function to infinitely recurse and result in a stack overflow...

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.

Question 3

quoting "The base case is a subarray containing fewer than two elements, that is, when p >= r"

How is "p >= r" possible? How is it possible for p (the start index) to be larger than r (the end index)?

Accepted Answer

p=r happens when a subarray has only one element
p > r happens when a subarray has no elements (if we have array[0..n-1], and n=0, then p=0,r=0-1=-1 and 0>-1)
in both case you want to stop trying to sort them

Question 4

I'm confused as to how the merge step sorts anything. Doesn't it need a rule to know how to sort the numbers (the rule being sorting them in ascending order)?

Accepted Answer

The merge step takes two sorted subarrays and produces one big sorted subarray with all those elements. It just repeatedly looks at the front of the two subarrays and takes the smallest element, until it runs out of elements. It only works because the two subarrays were already sorted.

In the example above (last merge) we have:
[3,7,12,14] and [2,6,9,11] being merged.
So, let's repeatedly take the smallest element from the front of the two arrays and remove them.
1st array, 2nd array, result
[3,7,12,14], [2,6,9,11], []
[3,7,12,14], [6,9,11], [2]
[7,12,14], [6,9,11], [2,3]
[7,12,14], [9,11], [2,3,6]
[12,14], [9,11], [2,3,6,7]
[12,14], [11], [2,3,6,7,9]
[12,14], [], [2,3,6,7,9,11]
[14], [], [2,3,6,7,9,11]
[], [], [2,3,6,7,9,11,14]

That's how it sorts

Question 5

Hi,

My program runs fine and the sorted array looks good. However I am getting an instruction in the beginning with respect to the code for calculating the midpoint.

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

Any idea what is the issue here?

Accepted Answer

p is the index of the 1st element of the subarray.
r is the index of the last element of the subarray 
Suppose p=2 and r=4 
q= floor( (p+r-1)/2) 
q= floor((2+4-1)/2)
q= floor( 5/2)
q= floor(2.5)
q= 2 
The above calculation gives a result of 2, but the midpoint of 2 and 4 should be 3 not 2.

Question 6

I used the correct code but the thing says "Maximum call stack exceeded."

Accepted Answer

There is unbounded recursion in your code somewhere. Check to make sure the recursion terminates.

Question 7

What about... `array.prototype.sort()`? Isn't that waaay easier? And numerical sort is just... `array.prototype.sort(function(a,b) {return a-b}` .

Accepted Answer

Someone had to program how the sort() function works.

Course: Computer science theory > Unit 1

Overview of merge sort

Want to join the conversation?