Description and implementation of a merge sort algorithm.

merge-sort.js

/**
 * Merge Sort: Gets its name from the process of repeatedly
 * splitting the original array and merging it back together.
 *
 * Process:
 * Repeatedly split the original array until all subarrays
 * are of just one element. Remerge the subarrays and 
 * continuously sort the elements.
 *
 * Performance:
 * Best Time Complexity: O(n*logn)
 * Average Time Complexity: O(n*logn)
 * Worst Time Complexity: O(n*logn)
 * Space Complexity: O(n)
 *
 * Visualization: https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/visualize/
 */

function mergeSort (array) {
  if (array.length > 1) {
    // Further split array
    const middleIndex = Math.floor(array.length / 2)
    let firstHalf = array.slice(0, middleIndex)
    let secondHalf = array.slice(middleIndex)
    // Recurse on both halves
    firstHalf = mergeSort(firstHalf)
    secondHalf = mergeSort(secondHalf)
    // Merge returned values
    const merged = merge(firstHalf, secondHalf)
    return merged
  } else {
    // Recursion base case
    return array
  }
}

function merge (array1, array2) {
  const mergedArray = []
  let i= 0
  let j = 0
  // Push values to merged array from two separate arrays
  // according to which value is less than the other.
  while (i < array1.length && j < array2.length) {
    if (array1[i] < array2[j]) {
      mergedArray.push(array1[i])
      i++
    } else {
      mergedArray.push(array2[j])
      j++
    }
  }

  // Push remaining values in first array
  for (; i < array1.length; i++) {
    mergedArray.push(array1[i])
  }

  // Push remaining values in second array
  for (; j < array2.length; j++) {
    mergedArray.push(array2[j])
  }
  return mergedArray
}

const data = Array.from({length: 10}, () => Math.random())

console.log('Unsorted:')
console.log(data)
console.log('Sorted:')
const sortedData = mergeSort(data)
console.log(sortedData)