The merge sort is one of the more advanced sorting algorithms that’s quite efficient in sorting large amounts of data. The algorithm uses **the recursive function concept with divide and conquer strategy** to efficiently sort a given list of elements.

To understand the concept of merge sort easily, let’s start with a small example array as follows:

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

First, split the array into two halves until there is only one element in each array:

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

Once done, start the second phase by merging and sorting two closest arrays. The smaller element will be pushed first to the new empty array, effectively sorting the array one step at a time.

Here’s an illustration of the merging:

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

Now that you know how the merge sort works, let’s see how you implement one using JavaScript.

## Implementation of merge sort using JavaScript

To implement merge sort using JavaScript, you need to first create a function that merges two arrays. Obviously, this function will accept two arrays, and it needs to sort the two arrays correctly starting from the smallest element.

Let’s first create the function and sort the arrays as follows:

```
function merge(left, right) {
let sortedArr = []; // the sorted elements will go here
while (left.length && right.length) {
// insert the smallest element to the sortedArr
if (left[0] < right[0]) {
sortedArr.push(left.shift());
} else {
sortedArr.push(right.shift());
}
}
}
```

When the `while`

loop above is finished, you would have the elements of two arrays sorted inside the `sortedArr`

variable. But since the two arrays length can be uneven, you may have one last element available in either `left`

or `right`

array:

Take a look at the following `merge()`

simulation:

```
merge([3, 4, 7], [2, 5]);
function merge(left, right) {
let sortedArr = []; // the sorted elements will go here
while (left.length && right.length) {
// insert the smallest element to the sortedArr
if (left[0] < right[0]) {
sortedArr.push(left.shift());
} else {
sortedArr.push(right.shift());
}
}
console.log(sortedArr); // [2, 3, 4, 5]
console.log(left); // [7]
console.log(right); // []
}
```

As you can see above, the `left`

element still has the number `7`

because there’s no element to compare with. To solve this problem, you can simply use the spread operator and put the leftover element into the mix:

```
function merge(left, right) {
let sortedArr = []; // the sorted elements will go here
while (left.length && right.length) {
// insert the smallest element to the sortedArr
if (left[0] < right[0]) {
sortedArr.push(left.shift());
} else {
sortedArr.push(right.shift());
}
}
// use spread operator and create a new array, combining the three arrays
return [...sortedArr, ...left, ...right];
}
```

With that, you have the `merge()`

function for the merge sort ready. Now you only need a function that splits an array into `1`

size.

Here’s an example of the `mergeSort()`

function:

```
function mergeSort(arr) {
const half = arr.length / 2;
// the base case is array length <=1
if (arr.length <= 1) {
return arr;
}
const left = arr.splice(0, half); // the first half of the array
const right = arr;
return merge(mergeSort(left), mergeSort(right));
}
```

The `mergeSort()`

function will first split the given array parameter in half until the array length is one or smaller. The arrays will then be passed to the `merge()`

function, which will start merging the arrays until all elements are merged.

And that’s how you implement a merge sort with JavaScript. Let’s look at the performance score of merge sort next.

## The efficiency of merge sort

The merge sort algorithm has the time complexity of `O(logN)`

, meaning that the time required to execute `N`

number of elements will rise in logarithmic proportion. If sorting an array of `10`

elements requires `1ms`

, sorting an array of `100`

elements will take `2ms`

.

Merge sort is much more efficient in time complexity than the insertion sort, but merge sort also consumes more space because the sorting is not in-place and the recursive call will be threaded. The merge sort will take `O(N)`

space to perform the sorting.

**Related articles:**