Merge Sort in JavaScript

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

Meher Howji avatar image
··- views
A random image as the post cover
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[0] and A[1] 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)