Q: The implementation in the challenge includes the following in the function `merge`: ``` for (i = 0; k <= q; i++, k++) { lowHalf[i] = array[k]; } for (j = 0; k <= r; j++, k++) { highHalf[j] = array[k]; } ``` doesn't that make the efficiency worse? I would expect another `n` term.

I don't think it will make much of a difference. The time complexity of creating these temporary array for merge sort will be O(n lgn). Since, all n elements are copied l (lg n +1) times. Which makes the the total complexity: O(n lgn) + O(n lgn) = O(2n lgn). And we know that constants doesn't impact our complexity substantially. So time complexity will still be O(n lgn).

Q: What if we didn't divide n by 2 at each step, but instead divided by 3? With this algorithm, "We start with subproblems of size n and repeatedly halve until we get down to subproblems of size 1.... the answer is l = lg n + 1. Would the answer to l be log base 3 of n instead of log base 2? This would make the runtime: O(n log base 3 n).

O(n log_2 n) and O(n log_3 n) are still just O(n log n ) because they only differ by a constant factor. Remember that we can convert log_a( x ) to log_b( x ) by multiplying by 1/( log_a(b) ) e.g. log_3 (9) = 1/(log_10(3)) * log_10 (9) = 2 One problem, that you may not be considering, with dividing the array in thirds is the problem you face when you want to merge the parts back together again. Before, with only 2 subarrays of size n/2 : - to merge them you had, at worst, to perform one comparison (to find the smallest element between the 2 subarrays) per element - 1 * n = n comparisons But with 3 subarrays of size n/3 : - now (supposing we do it in a straight forward manner), we have at worst, 2 comparisons (to find the smallest element between the 3 subarrays) per element - 2 * n = 2n comparisons. So we reduced our recursion depth by a factor of log(3)/log(2) = 1.585 But we increased our number of comparisons by a factor of 2 So overall we increased our running time by a factor of (2 * 1/1.585) or ~ 1.262 Hope this makes sense

Q: Can anyone please explain what constant c is? How to calculate it? Can anyone give where can I read about it or explain it on an example?

Suppose we had a chunk of code which added two numbers. e.g. `var a = 2 + 3` We could time how long this chunk of code took to run. We could use a stop watch, or we could give the computer instructions to time it for us. e.g. ``` //find the starting time in milliseconds var start = (new Date()).getTime(); //our chunk of code we are trying to measure var a = 2 + 3; //find the finish time var finish = (new Date()).getTime(); //this is the # of milliseconds it took the code to run var timeElapsed = finish - start; ``` We would expect this chunk of code to take about the same time every time we ran it. So we could say that this chunk of code runs in a constant amount of time. We could give that amount of time a label, e.g. we could call it c, or c1, or k. Let's call it c. If we ran that chunk of code n times, then the time it would take to complete would be: c * n The same type of thing is going on above in the article. During the merge, each element in the subarray will require some chunk of code to run that will require a constant amount of time to execute. We just give that constant amount of time the label c. You could measure it if you wanted too, but when we use asymptotic notation, we just ignore those constants. Hope this makes sense

Q: "To make things more concrete, let's say that the divide and combine steps together take cn time for some constant c." What does the author mean by to make things concrete, can't we use just the term n ?

Typically, when someone says they are making things more concrete, they mean that instead of talking in a theoretical sense, they will talk about a specific example. Θ(n) is a a set of functions (imagine a giant bag holding a bunch of functions), so, in theory, the discussion could be talking about any of the functions that are in Θ(n). To make the discussion more concrete, they reached their hand into the bag of functions Θ(n), and picked out the function "c*n", to use it as an example. The function "n" is also in Θ(n) so they could have used "n" too, but it usually good practice when analyzing an algorithm to use some constant multiple (like "c") of the most significant term to see what impact it has on the analysis, if any. Hope this makes sense

Q: Why is putting c before n (merge part) in the recursion necessary?

c is just a constant. So cn is just saying that the merge takes some constant amount of time per element being merged. If you just used n, it would be saying that the merge takes exactly 1 unit of time per element being merged.

Q: Hey, I've got the question: Why doesn't return the sorted array2 if the compiler accepts the code? [Edited to only show relevant code] ``` var arr2 = [17, 15, 14, 7, 4, 6]; merge(arr2, 0, Math.floor((0 + arr2.length-1) / 2), arr2.length-1); println("Second array after merging: " + arr2); Program.assertEqual(arr2, [4, 6, 7, 14, 15, 17]); ```

[17, 15, 14, 7, 4, 6] is an invalid input to the merge function, because the merge function require the two subarrays that are being merged to be sorted. In the above, neither of the two subarrays [17,15,14] or [7,4,6] are sorted. Invalid input = unexpected results.

Q: It keeps asking if the condition in while loop work if p is not 0. [Edited to only show relevant code] ``` while (i <= q && j <= r-q-1) { ... } ``` It passes the assertion but cannot proceed to next step in the challenge. Any hint?

The merge function is designed to merge two sub arrays: [p..q] and [q+1..r] The first while loop should stop when one of these arrays runs out of elements to pick from. Ask yourself: - How many elements are in a subarray that starts at index p and ends at index q ? - How many elements are in a subarray that starts at index q+1 and ends at index r ?.

Q: Help me to figure out, what am I doing wrong? it says 'Hm do all your assertion pass'? the code is: while(i<=(q-p)+1 && j<=r-q-1){ if(lowHalf[i]<highHalf[j]){ array[k]=lowHalf[i]; i++; } else { array[k]=highHalf[j]; j++; } k++; } while(i<=(q-p)+1){ array[k]=lowHalf[i]; i++; k++; } while(j<=(r-q-1)){ array[k]=highHalf[j]; j++; k++; } };

If you get "Hm do all your assertion pass?" that means one of your assertions is failing. Looking at the asserion that failed should help you diagnose the problem. Compare what the assertion expected vs what you actually got. If other assertions pass, then you can try to narrow down what the problem is even more. Is one of the elements missing in the actual result ? Which half did it come from ? What might cause that ? Good Luck

Question 1

Can someone please explain or clarify the content of the last paragraph? Working in place, taking space, etc.?
Many thanks.

Accepted Answer

That was the best 20 minute research answer I've ever read. Well done. I love the explanation.

Question 2

The implementation in the challenge includes the following in the function `merge`:
```
    for (i = 0; k <= q; i++, k++) {
        lowHalf[i] = array[k];
    }
    for (j = 0; k <= r; j++, k++) {
        highHalf[j] = array[k];
    }
```
doesn't that make the efficiency worse? I would expect another `n` term.

Accepted Answer

I don't think it will make much of a difference. The time complexity of creating these temporary array for merge sort will be O(n lgn). Since, all n elements are copied l (lg n +1) times.
Which makes the the total complexity: O(n lgn) + O(n lgn) = O(2n lgn).
And we know that constants doesn't impact our complexity substantially. So time complexity will still be O(n lgn).

Question 3

What if we didn't divide n by 2 at each step, but instead divided by 3?

With this algorithm, "We start with subproblems of size n and repeatedly halve until we get down to subproblems of size 1.... the answer is l = lg n + 1.

Would the answer to l be log base 3 of n instead of log base 2? This would make the runtime: O(n log base 3 n).

Accepted Answer

O(n log_2 n) and O(n log_3 n) are still just O(n log n )  because they only differ by a constant factor.
Remember that we can convert log_a( x ) to log_b( x ) by multiplying by 1/( log_a(b) ) 
e.g. log_3 (9) = 1/(log_10(3)) * log_10 (9) =  2

One problem, that you may not be considering, with dividing the array in thirds is the problem you face when you want to merge the parts back together again.

Before, with only 2 subarrays of size n/2 :
- to merge them you had, at worst, to perform one comparison (to find the smallest element between the 2 subarrays)  per element 
- 1 * n = n comparisons

But with 3 subarrays of size n/3 :
- now (supposing we do it in a straight forward manner), we have at worst, 2 comparisons (to find the smallest element between the 3 subarrays) per element
- 2 * n = 2n comparisons.

So we reduced our recursion depth by a factor of log(3)/log(2) =  1.585
But we increased our number of comparisons by a factor of 2
So overall we increased our running time by a factor of (2 * 1/1.585) or ~ 1.262

Hope this makes sense

Question 4

Can anyone please explain what constant c is? How to calculate it? Can anyone give where can I read about it or explain it on an example?

Accepted Answer

Suppose we had a chunk of code which added two numbers.
e.g. `var a = 2 + 3`
We could time how long this chunk of code took to run.
We could use a stop watch, or we could give the computer instructions to time it for us.
e.g.
```
//find the starting time in milliseconds
var start = (new Date()).getTime();

//our chunk of code we are trying to measure
var a = 2 + 3;

//find the finish time
var finish = (new Date()).getTime();
 //this is the # of milliseconds it took the code to run
var timeElapsed = finish - start;
```
We would expect this chunk of code to take about the same time every time we ran it.  So we could say that this chunk of code runs in a constant amount of time. We could give that amount of time a label, e.g. we could call it c, or c1, or k. Let's call it c.

If we ran that chunk of code n times, then the time it would take to complete would be:
 c * n

The same type of thing is going on above in the article. During the merge, each element in the subarray will require some chunk of code to run that will require a constant amount of time to execute. We just give that constant amount of time the label c. You could measure it if you wanted too, but when we use asymptotic notation, we just ignore those constants.

Hope this makes sense

Question 5

"To make things more concrete, let's say that the divide and combine steps together take cn time for some constant c." What does the author mean by to make things concrete, can't we use just the term n ?

Accepted Answer

Typically, when someone says they are making things more concrete, they mean that instead of talking in a theoretical sense, they will talk about a specific example.

Θ(n) is a a set of functions (imagine a giant bag holding a bunch of functions), so, in theory, the discussion could be talking about any of the functions that are in Θ(n). To make the discussion more concrete, they reached their hand into the bag of functions  Θ(n), and picked out the function "c*n", to use it as an example. The function "n" is also in Θ(n)  so they could have used "n" too, but it usually good practice when analyzing an algorithm to use some constant multiple (like "c") of the most significant term to see what impact it has on the analysis, if any.

Hope this makes sense

Question 6

Why is putting c before n (merge part) in the recursion necessary?

Accepted Answer

c is just a constant. So cn is just saying that the merge takes some constant amount of time per element being merged. If you just used n, it would be saying that the merge takes exactly 1 unit of time per element being merged.

Question 7

Hey, I've got the question: Why doesn't return the sorted array2 if the compiler accepts the code?
[Edited to only show relevant code]
```
var arr2 = [17, 15, 14, 7, 4, 6];
merge(arr2, 0, Math.floor((0 + arr2.length-1) / 2), arr2.length-1);
println("Second array after merging: " + arr2);
Program.assertEqual(arr2, [4, 6, 7, 14, 15, 17]);
```

Accepted Answer

[17, 15, 14, 7, 4, 6] is an invalid input to the merge function, because the merge function require the two subarrays that are being merged to be sorted. In the above, neither of the two subarrays [17,15,14] or [7,4,6] are sorted.

Invalid input = unexpected results.

Invalid input = unexpected results.

Question 8

It keeps asking if the condition in while loop work if p is not 0.

[Edited to only show relevant code]
```
    while (i <= q && j <= r-q-1) {
       ...
    }
  ```

It passes the assertion but cannot proceed to next step in the challenge.
Any hint?

Accepted Answer

The merge function is designed to merge two sub arrays:  [p..q] and [q+1..r]
The first while loop should stop when one of these arrays runs out of elements to pick from.

Ask yourself: 
- How many elements are in a subarray that starts at index p and ends at index q ?
- How many elements are in a subarray that starts at index q+1 and ends at index r ?.

Question 9

Help me to figure out, what am I doing wrong?
it says 'Hm do all your assertion pass'?
the code is:

while(i<=(q-p)+1 && j<=r-q-1){
        if(lowHalf[i]<highHalf[j]){
            array[k]=lowHalf[i];
            i++;
        }
        else {
            array[k]=highHalf[j];
            j++;
        }
        k++;
    }
    while(i<=(q-p)+1){
        array[k]=lowHalf[i];
        i++;
        k++;
        
    }
    while(j<=(r-q-1)){
        array[k]=highHalf[j];
        j++;
        k++;
    }
    
};

Accepted Answer

If you get "Hm do all your assertion pass?" that means one of your assertions is failing. Looking at the asserion that failed should help you diagnose the problem. Compare what the assertion expected vs what you actually got. If other assertions pass, then you can try to narrow down what the problem is even more.

Is one of the elements missing in the actual result ?
Which half did it come from ?
What might cause that ?

Good Luck

Is one of the elements missing in the actual result ?
Which half did it come from ? 
What might cause that ?

Good Luck

Computer science

Course: Computer science > Unit 1

Analysis of merge sort

Want to join the conversation?