## How Merge Sort works:

Divide and conquer

I am sure you have read this quote before. Apparently, it works in computer science as well. The algorithm divides the problem to smaller problems until it has to sort only two elements. After that it tries to merge the sorted elements.

## Merge Sort complexity:

The complexity of the algorithm is O(nlogn). To be precise the division is the O(logn) part. Every time the problem is divided by 2. The O(n) part is the merging of already sorted arrays.

## Implementation of Merge Sort in JavaScript

``````const mergesort = (array) => {
if (array.length <= 1) {
return array;
}

const middle = Math.floor(array.length / 2);
const left = array.slice(0, middle);
const right = array.slice(middle);

return merge(mergesort(left), mergesort(right));
};

const merge = (left, right) => {
let result = [];
let leftIndex = 0;
let rightIndex = 0;

while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}

return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
};

console.log(mergesort([4, 3, 2, 5, 9, 67, 8, 5, 40, 6, 6]));
// [2, 3, 4, 5,  5, 6, 6, 8, 9, 40, 67]
``````