# 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:

```
[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 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[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 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.

→ I wrote 17 books to help you become a better developer, download them all at $0 cost by joining my newsletter

→ **JOIN MY CODING BOOTCAMP**, an amazing cohort course that will be a huge step up in your coding
career - covering React, Next.js - next edition February 2025