# mergeSort

Mergesort is an optimized sorting algorithm which is a common choice to implement `sort` methods in standard libraries as an alternative to quicksort or heapsort.

Mergesort uses a divide-and-conquer strategy. It begins by treating the input list of length N as a set of N “sublists” of length 1, which are considered to be sorted. Adjacent sublists are then “merged” into sorted sublists of length 2, which are merged into sorted sublists of length 4, and so on, until only a single sorted list remains. (Note, if N is odd, an extra sublist of length 1 will be left after the first merge, and so on.)

Time complexity: The entire input must be iterated through n, and you’re narrowing the workload by half every time you merge so n * logn = O(nlogn).

1. Split array in half 2. Recursively sort each half
3. Merge sorted arrays into larger sorted array This can be implemented using either a recursive (“top-down”) or an iterative (“bottom-up”) approach.

Recursive Solution:

``````var mergeSort = function(array) {
if (array.length < 2) {
return array;
}

var mid = Math.floor(array.length / 2);
var left = array.slice(0, mid);
var right = array.slice(mid);
return merge(mergeSort(left), mergeSort(right));
};

var merge = function (left, right) {
var output = [];
var i = 0;
var j = 0;

while (left.length > i && right.length > j) {
if (left[i] < right[j]) {
output.push(left[i]);
i++;
} else{
output.push(right[j]);
j++;
}
}

return output.concat(left.slice(i)).concat(right.slice(j));
}``````