# Merge Sort in JavaScript

### Merge sort is a standard divide and conquer algorithm that scales.

··- views Photo by Jeremy Bezanger on Unsplash

## Overview

• It’s a standard recursive algorithm similar to binary search.
• The array is split until the pairs or individual item exist . The pairs are sorted.
• A merge routine then merges the 2 sorted arrays and this repeats until all the parts are merged.

## Merge Routine

The merge routine is as following for 2 sorted arrays: MIT Ref

| Left Sorted Array | Right Sorted Array | | ----------------- | ------------------ | | 20 | 12 | | 13 | 11 | | 7 | 9 | | 2 | 1 |

Steps to merge the left and right array:

• use 3 pointers for left half, right half and the resulting sorted array. YT Ref
• compare 1(i) & 2(j), strike off 1, push 1 at an index(k) in new array and move the pointer to 9
• compare 9 & 7, strike off 7, push 7 at an index(k) new array and move the pointer to 13
• repeat

## Code for Merge

• sorting will an easier operation as we are going to swap the A and A of the split array.
```function merge(input, leftHalf, rightHalf) {	var leftSize = leftHalf.length	var rightSize = rightHalf.length	var i = 0,		j = 0,		k = 0
while (i < leftSize && j < rightSize) {		if (leftHalf[i] <= rightHalf[j]) {			input[k] = leftHalf[i]			i++		} else {			input[k] = rightHalf[j]			j++		}		k++	}
while (i < leftSize) {		input[k] = leftHalf[i]		i++		k++	}
while (j < rightSize) {		input[k] = rightHalf[j]		j++		k++	}}```

## Code for Split and Sort Recursively

```function mergeSort(input) {	var leftHalf = []	var rightHalf = []	var remains = input.length % 2	var middle = (input.length + remains) / 2
if (input.length < 2) {		return input	}
for (var i = 0; i < middle; i++) {		leftHalf[i] = input[i]	}
for (var i = middle; i < input.length; i++) {		rightHalf[i - middle] = input[i]	}
mergeSort(leftHalf)	mergeSort(rightHalf)
merge(input, leftHalf, rightHalf)}```

## Final Complete Code

```var input = [2, 74, 12, 9, 1, 1, 1, 0, 9, 6, 5, 6, 6, 5]
function merge(input, leftHalf, rightHalf) {	var leftSize = leftHalf.length	var rightSize = rightHalf.length	var i = 0,		j = 0,		k = 0
while (i < leftSize && j < rightSize) {		if (leftHalf[i] <= rightHalf[j]) {			input[k] = leftHalf[i]			i++		} else {			input[k] = rightHalf[j]			j++		}		k++	}
while (i < leftSize) {		input[k] = leftHalf[i]		i++		k++	}
while (j < rightSize) {		input[k] = rightHalf[j]		j++		k++	}}
function mergeSort(input) {	var leftHalf = []	var rightHalf = []	var remains = input.length % 2	var middle = (input.length + remains) / 2
if (input.length < 2) {		return input	}
for (var i = 0; i < middle; i++) {		leftHalf[i] = input[i]	}
for (var i = middle; i < input.length; i++) {		rightHalf[i - middle] = input[i]	}
mergeSort(leftHalf)	mergeSort(rightHalf)
merge(input, leftHalf, rightHalf)}
mergeSort(input)console.log(input)```