# Bottoms Up Introduction to Merge Sort with JavaScript

## Merge

Let's say we have two sorted arrays...how would we merge the two?

``````[3, 8, 9]
[5, 50, 100]
``````

We can find the lowest number from both arrays and put it into a new merged array. Since the arrays are sorted, the lowest number of each array will be at the front. This means we just have to compare the first element in each sorted array to determine what the smallest number is.

``````[3, 8, 9]
[5, 50, 100]

[]
``````
``````// 3 is smaller than 5
[8, 9]
[5, 50, 100]


``````
``````// 5 is smaller than 8
[8, 9]
[50, 100]

[3, 5]
``````
``````// 8 is smaller than 50

[50, 100]

[3, 5, 8]
``````
``````// 9 is smaller than 50
[]
[50, 100]

[3, 5, 8, 9]
``````
``````// There's no more left in one of the arrays
[]
[50, 100]

[3, 5, 8, 9]
``````
``````// Just push the rest in
[]
[]

[3, 5, 8, 9, 50, 100]
``````

### Implementation

``````function merge(left, right) {
const output = [];

while(left.length && right.length) {
if(left <= right) {
output.push(left.shift());
} else {
output.push(right.shift());
}
}

while(left.length) {
output.push(left.shift());
}

while(right.length) {
output.push(right.shift());
}

return output;
}
``````

## Merge Sort

We know how to merge two sorted arrays, what does that have to do with merge sort? What do we do when we are given an array that is not sorted? How do we split it up into two sorted arrays?

We keep splitting the array in half until we come to a situation where there is only one element left in an array. When there's only one element in the array, we can ensure that it is sorted. If we have two arrays with one element each, it means that we can merge the two!

``````     [50, 8, 3, 5, 100, 9]
[50, 8, 3]          [5, 100, 9]
[50, 8]          [5, 100] 
              
``````

We can now merge  with  which turns into [8, 50]

``````     [50, 8, 3, 5, 100, 9]
[50, 8, 3]          [5, 100, 9]
[8, 50]          [5, 100] 
 
``````

Similarly we can merge  with  which turns into [5, 100]

``````     [50, 8, 3, 5, 100, 9]
[50, 8, 3]          [5, 100, 9]
[8, 50]          [5, 100] 
``````

Now lets merge [8, 50] with  which turns into [3, 8, 50]

``````     [50, 8, 3, 5, 100, 9]
[3, 8, 50]          [5, 100, 9]
[5, 100] 
``````

And merge [5, 100] with  which turns into [5, 9, 100]

``````     [50, 8, 3, 5, 100, 9]
[3, 8, 50]          [5, 9, 100]
``````

We are now left with two sorted arrays [3, 8, 50] and [5, 9, 100] which we can merge into [3, 5, 8, 9, 50, 100].

``````     [3, 5, 8, 9, 50, 100]
``````

### Implementation

``````function mergeSort(arr) {
if(arr.length < 2) {
return arr;
}
const middle = Math.floor(arr.length/2);
const left = arr.slice(0, middle);
const right = arr.slice(middle, arr.length);
return merge(mergeSort(left), mergeSort(right));
}
``````

## Full Implementation

``````function mergeSort(arr) {
if(arr.length < 2) {
return arr;
}
const middle = Math.floor(arr.length/2);
const left = arr.slice(0, middle);
const right = arr.slice(middle, arr.length);
return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
const output = [];

while(left.length && right.length) {
if(left <= right) {
output.push(left.shift());
} else {
output.push(right.shift());
}
}

while(left.length) {
output.push(left.shift());
}

while(right.length) {
output.push(right.shift());
}

return output;
}

console.log(mergeSort([50, 8, 3, 5, 100, 9]));
``````