utils/array-utils/src/insertSorted.js

  1. /**
  2.  * Insert the given element into the give array using the compareFunction.
  3.  * @param {Array} array - array in which to insert
  4.  * @param {*} element - element to insert into the array
  5.  * @param {Function} compareFunction - a function that defines the sort order of elements
  6.  * @alias module:array-utils.insertSorted
  7.  * @example
  8.  * const numbers = [1, 5]
  9.  * const result = insertSorted(numbers, 3, fnNumberSort)
  10.  */
  11. const insertSorted = (array, element, compareFunction) => {
  12.   let leftbound = 0
  13.   let rightbound = array.length
  14.   while (rightbound > leftbound) {
  15.     const testindex = Math.floor((leftbound + rightbound) / 2)
  16.     const testelement = array[testindex]
  17.     const compareresult = compareFunction(element, testelement)
  18.     if (compareresult > 0) { // element > testelement
  19.       leftbound = testindex + 1
  20.     } else {
  21.       rightbound = testindex
  22.     }
  23.   }
  24.   array.splice(leftbound, 0, element)
  25.   return array
  26. }
  28. module.exports = insertSorted