Merge sort is a sorting algorithm that uses the “divide and conquer” concept.

Given an array, we first divide it in the middle and we get two arrays.

We recursively perform this operation until we get to arrays of one element.

Then we start building up the sorted array from scratch, by ordering the individual items we got.

Suppose our array is this:

[4, 3, 1, 2]

We first divide the array into two arrays:

[4, 3]
[1, 2]

then we recursively divide those arrays:

[4]
[3]

and

[1]
[2]

Then it’s time to construct the result, by ordering those pairs of elements first:

[3, 4]
[1, 2]

Then we merge those two arrays:

[1, 2, 3, 4]

Let’s do another example with more items in the array, this time using letters:

['e', 'g', 'a', 'd', 'f', 'c', 'b']

We divide the array in half:

['e', 'g', 'a']
['d', 'f', 'c', 'b']

Then we divide the first array in half:

['e']
['g', 'a']

and we divide the second part:

['g']
['a']

We now take the second part of the original array and we divide it in half:

['d', 'f']
['c', 'b']

We divide both parts:

['d']
['f']

['c']
['b']

Now we have a list of 1-item arrays:

['e']
['g']
['a']
['d']
['f']
['c']
['b']

Now we order them in pairs:

['e', 'g']
['a', 'd']
['d', 'f']
['c', 'b']

Then we merge the first two arrays and the last two:

['a', 'd', 'e', 'g']
['c', 'b', 'd', 'f']

Finally we merge the two arrays we got:

['a', 'b', 'c', 'd', 'e', 'f', 'g']

We can implement this algorithm using two functions. The first is called mergeSort, which is the one we’ll call, and the other is called _mergeArrays, which takes care of merging the arrays. I prepended _ to its name to signal it’s not meant to be called directly.

Here they are:

const _mergeArrays = (a, b) => {
  const c = []

  while (a.length && b.length) {
    c.push(a[0] > b[0] ? b.shift() : a.shift())
  }

  //if we still have values, let's add them at the end of `c`
  while (a.length) {
    c.push(a.shift())
  }
  while (b.length) {
    c.push(b.shift())
  }

  return c
}

const mergeSort = (a) => {
  if (a.length < 2) return a
  const middle = Math.floor(a.length / 2)
  const a_l = a.slice(0, middle)
  const a_r = a.slice(middle, a.length)
  const sorted_l = mergeSort(a_l)
  const sorted_r = mergeSort(a_r)
  return _mergeArrays(sorted_l, sorted_r)
}

Notice how in _mergeArrays() we initialize a resulting array c that we fill with the values of the two arrays a and b we pass to the function, ordered by value. Calling shift() on an array will remove the first item in the array, returning it, so we pass it to c.push() to add it to the c array.

The complexity of this algorithm is O(n log(n)), which makes it very efficient.

Lessons in this unit:

0:	Introduction
1:	Linear Search
2:	Binary Search
3:	Bubble Sort
4:	Selection Sort
5:	▶︎ Merge Sort
6:	Quicksort
7:	Algorithm Complexity and Big O Notation