# Merge sort

## Definition

Merge sort is an efficient, general-purpose, comparison-based sorting algorithm. Merge sort is a divide and conquer algorithm, based on the idea of breaking down a array into several subarrays until each one consists of a single element and merging those subarrays in a manner that results into a sorted array.

## Implementation

```const mergeSort = arr => {
if (arr.length < 2) return arr;
const mid = Math.floor(arr.length / 2);
const l = mergeSort(arr.slice(0, mid));
const r = mergeSort(arr.slice(mid, arr.length));
return Array.from({ length: l.length + r.length }, () => {
if (!l.length) return r.shift();
else if (!r.length) return l.shift();
else return l[0] > r[0] ? r.shift() : l.shift();
});
};

mergeSort([5, 1, 4, 2, 3]); // [1, 2, 3, 4, 5]```

## Complexity

The algorithm has an average time complexity of `O(n log n)`, where `n` is the size of the input array.

## More like this

• Collection · 108 snippets

### JavaScript Arrays

Master array manipulation in JavaScript with this ES6 snippet collection.

• JavaScript ·

### Heap sort

Sort an array of numbers, using the heapsort algorithm.

• JavaScript ·

### Quick sort

Sort an array of numbers, using the quicksort algorithm.

• JavaScript ·

### Bucket sort

Sort an array of numbers, using the bucket sort algorithm.

Start typing a keyphrase to see matching snippets.