Q: Hello everyone! I've finished the challenge Implement Merge, but still the grader won't accept it. The result is correct, but still there seems to be something amiss. Is it the ++s? I haven;t used any fix numbers, so I can't seem to get where I am wrong... This is my code [Edited to only show relevant code] ``` while (...) { ... } while(i<j) { ... } while (j<i){ ... } }; ``` Thanks for your help!

The problem is the conditions in the 2nd and 3rd while loops. They will not always work because the size of the lowHalf and highHalf arrays will not always be equal.

Q: This doesn't work with arrays with 0 but it should I think: [Edited to show only relevant code] ``` var narray = [3, 15, 0, 7, 12, 14, 2, 6, 11]; merge(narray, 0, Math.floor((0 + narray.length-1) / 2), narray.length-1); println("Array after merging: " + narray); Program.assertEqual(narray, [0, 2, 3, 6, 7, 11, 12, 14, 15]); ```

Merge needs the lower half and upper half of the arrays to be sorted. If the upper and lower half are not sorted then merge will not work properly. Note the following: array= [3, 7, 12, 14, 2, 6, 9, 11] the lower half is: [3, 7, 12, 14] (note that it is sorted) the upper half is: [2, 6, 9, 11] (note that it is sorted) The lower half and upper half are sorted, so merge works as expected. Note the following: narray= [3, 15, 0, 7, 12, 14, 2, 6, 11] the lower half is: [3, 15, 0, 7, 12] (note that it is NOT sorted) the upper half is: [14, 2, 6, 11 ] (note that it is NOT sorted) The lower half and upper half are not sorted, so merge does not work as expected. Hope this makes sense

Q: Earlier we learned about insertion sort. Would the efficiency or complexity be any different if we did NOT use "temporary arrays", but instead simply: - insertion sort the already-sorted lowHalf into the already-sorted highHalf?

The merge algorithm doesn't care how the lowHalf and highHalf arrays were sorted It will merge two sorted arrays in O(n) If you were trying to sort an array by: - splitting the array into two halves - insertion sort each half - merge the two halves together The complexity would be O(n^2) (which is worse than merge sorts's O(n log n) ) Why ? Each half has n/2 elements, and sorting n/2 elements using a n^2 algorithm is O(n^2). O( (n/2)^2) = O( n^2/4 ) = O (n^2) (we drop the constants) Hope this answers your question

Q: Has anyone ever finished this task? The result I get is correct, the array is successfully merged and sorted but I can't go to the next step!

Depending on the array being merged, either the 2nd or 3rd while loop won't be entered. There is probably a mistake in the one that is not being used (it's not being used so you don't see a problem in the output). Double check that you are using the correct indexes.

Q: In next challenge, when the array have two same elements, the function will don't work how can I modify it? thanks in advance! XD ``` // Takes in an array that has two sorted subarrays, // from [p..q] and [q+1..r], and merges the array var merge = function(array, p, q, r) { var lowHalf = []; var highHalf = []; var k = p; var i; var j; for (i = 0; k <= q; i++, k++) { lowHalf[i] = array[k]; } for (j = 0; k <= r; j++, k++) { highHalf[j] = array[k]; } k = p; i = 0; j = 0; // Repeatedly compare the lowest untaken element in // lowHalf with the lowest untaken element in highHalf // and copy the lower of the two back into array while (i < lowHalf.length && j < highHalf.length) { if (lowHalf[i] <= highHalf[j]) { array[k++] = lowHalf[i++]; } else { array[k++] = highHalf[j++]; } } // Once one of lowHalf and highHalf has been fully copied // back into array, copy the remaining elements from the // other temporary array back into the array while (i < lowHalf.length) { array[k++] = lowHalf[i++]; } while (j < highHalf.length) { array[k++] = highHalf[j++]; } }; var array = [3, 7, 12, 14, 2, 6, 9, 11]; merge(array, 0, Math.floor((0 + array.length-1) / 2), array.length-1); println("Array after merging: " + array); Program.assertEqual(array, [2, 3, 6, 7, 9, 11, 12, 14]); var array2 = [3, 9, 1, 4]; merge(array2, 0, Math.floor((0 + array2.length-1) / 2), array2.length-1); println("Array2 after merging: " + array2); Program.assertEqual(array2, [1, 3, 4, 9]); ```

It works for me. Which array with the two same elements were you trying to merge ?

Q: Until I began studying algorithms here, I had always read and heard that you should avoid mutating the original list, array, or collection while performing any sort of logic on it. For instance, I would typically return a copy of the original array here that is sorted. Is there a reason this isn't practiced in these lessons?

There's nothing wrong with functions that mutate their inputs, as long as it is clear to the user that the inputs will be modified. They are used all the time. Of course, there are many cases where the user doesn't want the original inputs modified. In these cases, it would be fairly easy to wrap a function around the mutator function that does the following: 1) make copies of original inputs 2) pass copies of inputs to mutator function 3) return results of mutator function The reason you wouldn't always make copies of the inputs are: - making copies consumes memory and takes time e.g. copying an array requires O(n) space and O(n) time When writing algorithms you are typically trying to minimize the use of space and time. Hope this makes sense P.S. I would be curious to see examples where books have said to avoid using mutators

Q: Is it the basic learning of computer science. here var , array, ()small brackets{}big brackets[] are learned. Where to start if i dont know about what is computer science i am diploma in mechanical. I wanna start learning this where i can understand c html css.Please help

Before learning computer science, you will want learn programming: Here is a JavaScript course: https://www.khanacademy.org/computing/computer-programming/programming If you want to learn html/css try this course: https://www.khanacademy.org/computing/computer-programming/html-css For a course in C (not on khan academy) try: https://www.youtube.com/watch?v=2NWeucMKrLI&list=PL6gx4Cwl9DGAKIXv8Yr6nhGJ9Vlcjyymq

Question 1

I feel like I cheated the grader...
[Edited to remove solution for first step]

The code worked OK for the first step, but on the second one, where I used negative numbers and 0, it went haywire. 
It wouln't put zero where it had to and a 1 I used also was mislocated. I deleted both of them from my array, (it was [3, 3, -5, -1, 1, 0 14, 5] initially) and then it was properly sorted and the evaluator let me pass. 
But I still feel like I did something wrong and just cheated to pass.
Can any one tell me where I was wrong?

Accepted Answer

No issue with your merge function, but there are issues with how you are trying to use it.

Merge requires the lower half and upper half of the array to be sorted before it is called. If the lower half and upper half aren't initially sorted then it will behave unpredictably.
So for  [3, 3, -5, -1, 1, 0 14, 5]: 
- the lower half: [3,3,-5,-1] is not sorted
- the upper half: [1,0,14,15] is not sorted
So we shouldn't expect merge to work properly. You might get lucky and it might still end up as a sorted array, but it would just be coincidence.

Question 2

Hello,

I'd like to ask for some help or hints! I've been working on the 'Implement Merge' challenge and I got at least somewhere with my code. However, somewhere there must be still be a mistake (or two hehe), because the grader is not passing me onto the second step. I am not getting any oh noes or hints in the program itself, so I find it quite hard to figure out what I have to do. This is my code so far: (only showing the while loops):
[Edited to only show relevant code]
```
...
    while(lowHalf.length !== i && highHalf.length !== j){
       ...
    }
    
    while(lowHalf.length !== i){
        ...
    }
    while(highHalf.length !== j){
        ...
    }
   ...
};
```

Thank you in advance!

Accepted Answer

The code is technically correct, but the conditions you are using are fairly unusual, so the grader isn't expecting them. 
e.g. It is unusual to see someone use  `lowHalf.length !== i`  instead of `i < lowHalf.length`
 
`i < lowHalf.length` is generally preferred, because it is safer. Here's why:
- `lowHalf.length !== i` will only stop when i is exactly equal to the length of the array, so if i was ,by accident, larger than the length of the array this condition would pass, and bad things like trying to access elements not in the array could occur ( in a programming language like C or C++ this could have serious consequences)
-on the other hand `i < lowHalf.length` would fail if , by accident, i was larger than the length of the array, thus preventing potential disaster

Hope this makes sense

Question 3

Hello everyone!
I've finished the challenge Implement Merge, but still the grader won't accept it. The result is correct, but still there seems to be something amiss. Is it the ++s? I haven;t used any fix numbers, so I can't seem to get where I am wrong...

This is my code
[Edited to only show relevant code]
```
    while (...)
    {
        ...
    }
    
   while(i<j) {
        ...
    }
    while (j<i){
       ...
    }
    
};
``` 
Thanks for your help!

Accepted Answer

The problem is the conditions in the 2nd and 3rd while loops.
They will not always work because the size of the lowHalf and highHalf arrays will not always be equal.

Question 4

This doesn't work with arrays with 0 but it should I think:

[Edited to show only relevant code]
```
var narray = [3, 15,  0, 7, 12, 14, 2, 6, 11];
merge(narray, 0, Math.floor((0 + narray.length-1) / 2), narray.length-1);
println("Array after merging: " + narray);
Program.assertEqual(narray, [0, 2, 3, 6, 7, 11, 12, 14, 15]);
```

Accepted Answer

Merge needs the lower half and upper half of the arrays to be sorted.
If the upper and lower half are not sorted then merge will not work properly.

Note the following:
array= [3, 7, 12, 14, 2, 6, 9, 11]
the lower half is:  [3, 7, 12, 14] (note that it is sorted)
the upper half is:  [2, 6, 9, 11] (note that it is sorted)
The lower half and upper half are sorted, so merge works as expected.

Note the following:
narray= [3, 15, 0, 7, 12, 14, 2, 6, 11]
the lower half is:  [3, 15, 0, 7, 12]  (note that it is NOT sorted)
the upper half is:  [14, 2, 6, 11 ]  (note that it is NOT sorted)
The lower half and upper half are not sorted, so merge does not work as expected.

Hope this makes sense

Question 5

Earlier we learned about insertion sort. Would the efficiency or complexity be any different if we did NOT use "temporary arrays", but instead simply:
- insertion sort the already-sorted lowHalf into the already-sorted highHalf?

Accepted Answer

The merge algorithm doesn't care how the lowHalf and highHalf arrays were sorted
It will merge two sorted arrays in O(n)

If you were trying to sort an array by:
- splitting the array into two halves
- insertion sort each half
- merge the two halves together
The complexity would be O(n^2) (which is worse than merge sorts's O(n log n) )
Why ?
Each half has n/2 elements, and sorting n/2 elements using a n^2 algorithm is O(n^2).
O( (n/2)^2) = O( n^2/4 ) = O (n^2)  (we drop the constants)

Hope this answers your question

Question 6

Has anyone ever finished this task?
The result I get is correct, the array is successfully merged and sorted but I can't go to the next step!

Accepted Answer

Depending on the array being merged, either the 2nd or 3rd while loop won't be entered. There is probably a mistake in the one that is not being used (it's not being used so you don't see a problem in the output). Double check that you are using the correct indexes.

Question 7

In next challenge, when the array have two same elements, the function will don't work
how can I modify it? thanks in advance!  XD

```
// Takes in an array that has two sorted subarrays,
//  from [p..q] and [q+1..r], and merges the array
var merge = function(array, p, q, r) {
    var lowHalf = [];
    var highHalf = [];

var k = p;
    var i;
    var j;
    for (i = 0; k <= q; i++, k++) {
        lowHalf[i] = array[k];
    }
    for (j = 0; k <= r; j++, k++) {
        highHalf[j] = array[k];
    }

k = p;
    i = 0;
    j = 0;
    
    // Repeatedly compare the lowest untaken element in
    //  lowHalf with the lowest untaken element in highHalf
    //  and copy the lower of the two back into array
    while (i < lowHalf.length && j < highHalf.length) {
        if (lowHalf[i] <= highHalf[j]) {
            array[k++] = lowHalf[i++];
        } else {
            array[k++] = highHalf[j++];
        }
    }

// Once one of lowHalf and highHalf has been fully copied
    //  back into array, copy the remaining elements from the
    //  other temporary array back into the array
    
    while (i < lowHalf.length) {
        array[k++] = lowHalf[i++];
    }
    
    while (j < highHalf.length) {
        array[k++] = highHalf[j++];
    }
    
};

var array = [3, 7, 12, 14, 2, 6, 9, 11];
merge(array, 0,
    Math.floor((0 + array.length-1) / 2),
    array.length-1);
println("Array after merging: " + array);
Program.assertEqual(array, [2, 3, 6, 7, 9, 11, 12, 14]);

var array2 = [3, 9, 1, 4];
merge(array2, 0,
    Math.floor((0 + array2.length-1) / 2),
    array2.length-1);
println("Array2 after merging: " + array2);
Program.assertEqual(array2, [1, 3, 4, 9]);

```

Accepted Answer

It works for me. Which array with the two same elements were you trying to merge ?

Question 8

Until I began studying algorithms here, I had always read and heard that you should avoid mutating the original list, array, or collection while performing any sort of logic on it. For instance, I would typically return a copy of the original array here that is sorted. Is there a reason this isn't practiced in these lessons?

Accepted Answer

There's nothing wrong with functions that mutate their inputs, as long as it is clear to the user that the inputs will be modified. They are used all the time. Of course, there are many cases where the user doesn't want the original inputs modified. In these cases,  it would be fairly easy to wrap a function around the mutator function that does the following:
1) make copies of original inputs
2) pass copies of inputs to mutator function
3) return results of mutator function

The reason you wouldn't always make copies of the inputs are:
- making copies consumes memory and takes time 
e.g. copying an array requires O(n) space and O(n) time

When writing algorithms you are typically trying to minimize the use of space and time.

Hope this makes sense

P.S. I would be curious to see examples where books have said to avoid using mutators

Question 9

Is it the basic learning of computer science. here var , array, ()small brackets{}big brackets[] are learned. Where to start if i dont know about what is computer science i am diploma in mechanical.  I wanna start  learning this where i can understand c html css.Please help

Accepted Answer

Before learning computer science, you will want learn programming: 
Here is a JavaScript course:
https://www.khanacademy.org/computing/computer-programming/programming

If you want to learn html/css try this course:
https://www.khanacademy.org/computing/computer-programming/html-css

For a course in C (not on khan academy) try:
https://www.youtube.com/watch?v=2NWeucMKrLI&list=PL6gx4Cwl9DGAKIXv8Yr6nhGJ9Vlcjyymq

Computer science

Course: Computer science > Unit 1

Linear-time merging

Want to join the conversation?