Merge Sort in JavaScript

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)