Merge sort implementation example (adapted from “Algorithms, Part I” course)

mergeSort.js

// Adapted from “Algorithms, Part I” course by “Princeton University” on coursera.org

const defaultCompare = (a, b) =>
  a < b ? -1 : 1

const merge = (arr, aux, compare, low, mid, high) => {
  // left and right half scan indices
  let l = low, r = mid + 1

  // copy into auxillary array  
  for (let i = low; i <= high; i++) aux[i] = arr[i];
  
  for (let i = low; i <= high; i++) {
    if      (l > mid)                     arr[i] = aux[r++]; // left half exhausted
    else if (r > high)                    arr[i] = aux[l++]; // right half exhausted
    else if (compare(aux[r], aux[l]) < 0) arr[i] = aux[r++]; // right half’s current smalller
    else                                  arr[i] = aux[l++]; // left half’s current smalller or both equal
  }
}

const sort = (arr, aux, compare, low, high) => {
  if (high <= low) return
  let mid = Math.floor(low + (high - low) / 2)

  sort(arr, aux, compare, low, mid)
  sort(arr, aux, compare, mid + 1, high)
  merge(arr, aux, compare, low, mid, high)
}

/**
 * Function to compare array alements with while sorting
 * @callback compareFunction
 * @param {*} a - first element to compare
 * @param {*} b - second element to compare
 * @return {(-1|1)} -1 if (a < b), +1 if (b > a), a == b comparison not required
 */

/**
 * Immutably sort an array using merge sort (stable)
 * @param {Array} arr - array to sort
 * @param {compareFunction} [compare=defaultCompare] - function to compare elements
 * @return {Array} sorted array copy
 */
export default (arr, compare = defaultCompare) => {
  const clone = arr.slice()
  const aux = [...new Array(clone.length)]
  sort(clone, aux, compare, 0, clone.length - 1)
  return clone
}