# JavaScript Algorithms: Merge Sort

> Learn how merge sort works in JavaScript, a divide and conquer algorithm that splits the array, sorts the halves, and merges them in O(n log n) time.

Author: [Flavio Copes](https://flaviocopes.com/about/) | Published: 2020-11-24 | Topics: [JavaScript](https://flaviocopes.com/tags/js/) | Canonical: https://flaviocopes.com/merge-sort-javascript/

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:

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