# JavaScript Algorithms: Merge Sort

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 2 arrays.

We recursively perform this operation, until we get to arrays of 1 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 2 arrays:

``````[4, 3]
[1, 2]
``````

then we recursively divide those arrays:

``````

``````

and

``````

``````

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

``````[3, 4]
[1, 2]
``````

Then we merge those 2 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 2:

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

Then we divide the first array in 2:

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

and we divide the second result:

``````['g']
['a']
``````

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

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

We divide both items:

``````['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 order the first 2 arrays and the last 2:

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

Finally we merge the 2 arrays we got:

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

We can implement this algorithm using 2 functions. The first called `mergeSort`, which is the function we'll call, and another one 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 > b ? 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 2 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.

THE VALLEY OF CODE

THE WEB DEVELOPER's MANUAL

You might be interested in those things I do:

• Learn to code in THE VALLEY OF CODE, your your web development manual
• Find a ton of Web Development projects to learn modern tech stacks in practice in THE VALLEY OF CODE PRO
• I wrote 16 books for beginner software developers, DOWNLOAD THEM NOW
• Every year I organize a hands-on cohort course coding BOOTCAMP to teach you how to build a complex, modern Web Application in practice (next edition February-March-April-May 2024)
• Learn how to start a solopreneur business on the Internet with SOLO LAB (next edition in 2024)
• Find me on X