FAQ: Merge Sort: JavaScript - Review

This community-built FAQ covers the “Review” exercise from the lesson “Merge Sort: JavaScript”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Pass the Technical Interview with JavaScript

FAQs on the exercise Review

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 (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 (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 (like) to up-vote the contribution!

Need broader help or resources? Head to Language Help and Tips and Resources. If you are wanting feedback or inspiration for a project, check out Projects.

Looking for motivation to keep learning? Join our wider discussions in Community

Learn more about how to use this guide.

Found a bug? Report it online, or post in Bug Reporting

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

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();

Same goes for the rightArray portion. I had to Google this and found info on this here: javascript - Is there a way to method chain .push and .shift array methods? - Stack Overflow.

The shift() array method returns the shifted element whilst also mutating the array.

Therefore you can combine the two processes within the push method.

// Original
sortedArray.push(leftArray[0]);
leftArray.shift();

// Combined
sortedArray.push(leftArray.shift());

You can also use the conditional (ternary) operator to get the whole if else conditional into one line if you like:

leftArray[0] < rightArray[0] ? sortedArray.push(leftArray.shift()) : sortedArray.push(rightArray.shift());
2 Likes
return sortedArray.concat(leftArray).concat(rightArray);

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?

Hello fellow coder,

I’m sorry to dig up this post almost a year later. :sweat:
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. :thinking:

Thank in advance to any good soul who will answer. :pray:

I have returned to this with fresh eyes…

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.

1 Like

Thank you for your explanation and for taking the time to come back to this old post!
It’s much clearer to me now :+1:

1 Like

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.