# Merge Sort in JavaScript

··· Likes

## 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 ArrayRight Sorted Array
2012
1311
79
21

Steps to merge the left and right array:

## 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)``````