There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply () below.
If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.
Join the Discussion. Help a fellow learner on their journey.
Ask or answer a question about this exercise by clicking reply () below!
You can also find further discussion and get answers to your questions over in Language Help.
Agree with a comment or answer? Like () to up-vote the contribution!
Q: In index.js, we included the solution code from the last exercise. If you’re up for the challenge, see if you can combine the two lines in your if and else blocks into one line to make your code look a little cleaner.
A: Use a comma to separate the two lines.
// Original
sortedArray.push(leftArray[0]);
leftArray.shift();
// Combined
sortedArray.push(leftArray[0]), leftArray.shift();
Why does the solution concatenate the three arrays at the end of merge()? We’re removing all the elements from our left- and right- arrays as they are sorted, so doesn’t this operation just add nothing to the returned array?
I’m sorry to dig up this post almost a year later.
But I’m also interested in the answer to this question and I’m hoping that someone gonna will explain it.
Why do we need to concatenate the three arrays at the end of merge()? I try to console.log at every step the sortedArray or the left and right array but it didn’t make sense to me. And it doesn’t work without concatenate so it’s sure there is something I missing out.
Thank in advance to any good soul who will answer.
During the merge steps, it is often the case that one of the arrays to be merged will run out of elements before the other because it happens to have lower values in it, or because there is an odd number of elements. For example [5, 9] and [10, 12] will become [] and [10, 12] after two iterations of the merge loop as the left array has the lower value both times.
These left-over elements cannot be meaningfully compared against an other (empty) array as the result is always false:
undefined < 0 // false
undefined > 0 // false
The left-over values are already sorted from previous recursions of the merge step, so they can just be appended to the end of the return array.
I tried to do a code a Merge Sort for a linked list, based on the algorithm in the lesson.
I came up with this in-place sort, inspired by the Java version of this lesson.
function sort(list) {
if (!list) { // (base case)
return null;
}
const head = (list instanceof LinkedList) ? list.head : list;
if (!head) {
return null;
}
// find middle node
let i = 0;
let middleNode = null;
let previous = head;
let current = head.getNextNode();
i++;
if (current) {
middleNode = head;
previous = current;
current = current.getNextNode();
i++;
}
else { // if no next node, return head (base case)
return head;
}
while(current) {
previous = current;
current = current.getNextNode();
if (i % 2 == 0) { // move forward every other time
middleNode = middleNode.getNextNode();
}
i++;
}
// previous is now the tail node
// middleNode is now the middle node, i is length of list
const rightHead = middleNode.getNextNode();
// split list into 2 lists, by ending list at middleNode
middleNode.setNextNode(null);
const result = merge(sort(head), sort(rightHead));
if (list instanceof LinkedList) {
list.head = result;
//return list;
}
return result;
}
function merge(left, right) {
// left is left list's head node, right is right list's head node
if (!right) {
return left;
}
else if (!left) {
return right;
}
let head = null; // head node for combined list
let current = null;
// left is pointer for current left node being compared
// right is pointer for current right node being compared
if (left.data <= right.data) {
head = left;
current = left;
left = left.getNextNode();
}
else {
head = right;
current = right;
right = right.getNextNode();
}
while (left && right) {
if (left.data <= right.data) {
current.setNextNode(left);
current = left; // current moves to its next node
left = left.getNextNode();
}
else {
current.setNextNode(right);
current = right; // current moves to its next node
right = right.getNextNode();
}
}
// if nodes remain in one of left or right, add them to end
if (left) {
current.setNextNode(left);
}
else if (right) {
current.setNextNode(right);
}
// already have null to end this "list"
return head;
}
I guess I could have put the finding the middle node of the list as a separate function.
) below.
) to up-vote the contribution!
