Merge Sort in JavaScript

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

Meher Howji avatar image
··· 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 RefExternal link icon

Left Sorted ArrayRight Sorted Array
2012
1311
79
21

Steps to merge the left and right array:

  • use 3 pointers for left half, right half and the resulting sorted array. YT RefExternal link icon
  • 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)