Skip to the content
Start

Merge sort

JavaScript · Unit 22: Searching and sorting

Two lists that already come sorted can be joined into one without sorting anything again: look at the front of each and take the smaller.

Since both are sorted, the smaller front is the smallest of everything left.

const a = [2, 8];
const b = [3, 5];
const res = [];
if (a[0] <= b[0]) {
  res.push(a.shift());
} else {
  res.push(b.shift());
}
console.log(res, a, b);

Prints

[ 2 ] [ 8 ] [ 3, 5 ]

The rest of the explanation is in the lesson, which is part of the full plan.

Exercises in this lesson

You do them in the app, which checks them on the spot and explains why.

  1. 1. Complete the code

    Complete it so the merge always takes the smaller of the two fronts.

  2. 2. Predict the output

    Two lists get merged, and then both originals get printed. What does it print?

  3. 3. Find the bug

    merge should join both complete lists and give [ 2, 3, 5, 8 ]. Which line has the error?

  4. 4. Multiple choice

    Merging two sorted lists of 50 numbers each, how much work is that?

  5. 5. Put the lines in order

    Put in order the function that cuts a list into two halves and returns them inside an array, the left one first.

  6. 6. Predict the output

    Every call prints the list it got. What does it print?

  7. 7. Complete the code

    Complete it so the left half reaches the merge already sorted.

  8. 8. Find the case that fails

    sortAll(ns) returns a new list with the numbers from smallest to largest; with an empty list it returns an empty list. Which call does it fail on?

  9. 9. Predict the output

    The list gets sorted and then the original gets printed. What does it print?

Do this lesson

It opens in your browser. This lesson is part of the full plan; the first unit of each course is free.

See all lessons →