IntroSort.js

/**
 * @function Introsort (As implemented in STD C++ Lib)
 * The function performs introsort which is used in
 * C++ Standard LIbrary, the implementation is inspired from]
 * library routine itself.
 * ALGORITHM:
 * 1) It performs quicksort on array until the recursion depth
 *    exceeds a pre determined limit.
 * 2) If the limit is reached it switches to heapsort
 * 3) For array size less than a threshold(16) directly
 *    does insertion sort on array
 * @param {Array} array the array to be sorted
 * @param {Function} compare the comparison function
 *
 * @see [Introsort](https://en.wikipedia.org/wiki/Introsort)
 * @author [Lakhan Nad](https://github.com/Lakhan-Nad)
 */
function introsort (array, compare) {
  /**
   * @function Default Comparison Function
   * This function is same as implemented by
   * Array.sort method
   * @see [StackOverflow](https://stackoverflow.com/questions/47334234/how-to-implement-array-prototype-sort-default-compare-function)
   * @param {*} a variable 1
   * @param {*} b variable 2
   * @returns {Number}
   * -1 if a is less than b
   *  0 if a is equal to b
   *  1 if a greater than b
   */
  const defaultComparator = function (x, y) {
    if (x === undefined && y === undefined) return 0
    if (x === undefined) return 1
    if (y === undefined) return -1
    const xString = toString(x)
    const yString = toString(y)
    if (xString < yString) return -1
    if (xString > yString) return 1
    return 0
  }
  /**
   * @function helper function for defaultComparator
   * Converts a given object to String
   * @throws TypeError()
   * @param {Object} obj
   * @returns {String} String representation of given object
   */
  const toString = function (obj) {
    if (obj === null) return 'null'
    if (typeof obj === 'boolean' || typeof obj === 'number') {
      return obj.toString()
    }
    if (typeof obj === 'string') return obj
    if (typeof obj === 'symbol') throw new TypeError()
    return obj.toString()
  }
  /**
   * Checks if the value passed is an array
   * or not
   */
  if (Array.isArray(array) === false) {
    return
  }
  /**
   * If the compare parameter is not a function
   * or not passed at all use default comparator
   * function
   */
  if (typeof compare !== 'function') {
    compare = defaultComparator // If compare is not a comparator function
  }
  /**
   * Use a closure to define the whole sort
   * implementation this is done through
   * [IIFE](https://en.wikipedia.org/wiki/Immediately_invoked_function_expression)
   */
  return (function (array, comparator) {
    const swap = function (index1, index2) {
      const temp = array[index1]
      array[index1] = array[index2]
      array[index2] = temp
    }
    /**
     * @constant THRESHOLD
     * If the length of array is less than
     * this then we simply perform insertion sort
     */
    const THRESHOLD = 16
    /**
     * @constant TUNEMAXDEPTH
     * Constant used to increase or decrease value
     * of maxDepth
     */
    const TUNEMAXDEPTH = 1
    const len = array.length
    /**
     * Return if array is only of length 1
     * Array of size 1 is always sorted
     */
    if (len === 1) {
      return
    }
    /**
     * Calculate maxDepth = log2(len)
     * Taken from implementation in stdc++
     */
    const maxDepth = Math.floor(Math.log2(len)) * TUNEMAXDEPTH
    /**
     * The very first call to quicksort
     * this initiates sort routine
     */
    quickSort(0, len, maxDepth)
    /**
     * A final check call to insertion sort
     * on sorted array
     */
    insertionSort(0, len)
    /** *********************  Implementation of various routines  **************************/
    /**
     * @function
     * This is recursive quicksort implementation in array
     * of segment [start,last-1]
     * [QuickSort](https://en.wikipedia.org/wiki/Quicksort)
     * @param {Number} start the start index of array segment to be sorted
     * @param {Number} last  one more than the last index of array segment
     * @param {Number} depth this measures how many recursive calls are done
     */
    function quickSort (start, last, depth) {
      if (last - start <= THRESHOLD) {
        insertionSort(start, last)
        return
      } else if (depth <= 0) {
        heapSort(start, last)
        return
      }
      let pivot = (last + start) >> 1
      pivot = partition(start, last, pivot)
      quickSort(start, pivot, depth - 1)
      quickSort(pivot + 1, last, depth - 1)
    }
    /**
     * @function Helper function to quicksort
     * @param {Number} start the start of array segment to partition
     * @param {Number} last  one more than last index of the array segment
     * @param {Number} pivot the index of pivot to be used
     * @returns {Number} the index of pivot after partition
     */
    function partition (start, last, pivot) {
      swap(start, pivot)
      pivot = start
      let lo = start
      let hi = last
      while (true) {
        lo++
        while (comparator(array[lo], array[pivot]) <= 0 && lo !== last) {
          lo++
        }
        hi--
        while (comparator(array[hi], array[pivot]) > 0 && hi !== start) {
          hi--
        }
        if (lo >= hi) {
          break
        }
        swap(lo, hi)
      }
      swap(start, hi)
      return hi
    }
    /**
     * @function
     * Performs insertion sort on array of range
     * [start, last-1]
     * @param {Number} start the first index of array segment to be sorted
     * @param {Number} last  one more than last index of array to be sorted
     */
    function insertionSort (start, last) {
      let i, j
      for (i = start + 1; i < last; i++) {
        j = i - 1
        while (j >= 0 && comparator(array[j], array[j + 1]) > 0) {
          swap(j, j + 1)
          j--
        }
      }
    }
    /**
     * @function
     * Performs heapsort in array segment of range [start, last-1]
     * [HeapSort](https://en.wikipedia.org/wiki/Heapsort)
     * @param {Number} start the first index of array segment to be sorted
     * @param {Number} last  one more than last index of array to be sorted
     */
    function heapSort (start, last) {
      let x = (last + start) >> 1
      while (x - start >= 0) {
        heapify(x, start, last)
        x--
      }
      x = last - 1
      while (x - start > 0) {
        swap(start, x)
        heapify(start, start, x)
        x--
      }
    }
    /**
     * @function Helper function to heapsort routine
     * @param {Number} cur the index we need to heapify
     * @param {Number} start the start index of array segment that cur belongs to
     * @param {Number} last  one more than last index of segment that cur belongs to
     */
    function heapify (cur, start, last) {
      const size = last - start
      let max, lt, rt
      cur = cur - start
      while (true) {
        max = cur
        lt = 2 * max + 1
        rt = 2 * max + 2
        if (
          lt < size &&
          comparator(array[start + max], array[start + lt]) < 0
        ) {
          max = lt
        }
        if (
          rt < size &&
          comparator(array[start + max], array[start + rt]) < 0
        ) {
          max = rt
        }
        if (max !== cur) {
          swap(start + cur, start + max)
          cur = max
        } else {
          break
        }
      }
    }
  })(array, compare)
}

/**
 * @example Demo run of the sort routine
 * The data is randomly generated
 * Returns 'RIGHT:)' if the sort routine worked as expected,
 *         'WRONG!!' otherwise
 */
function demo1 () {
  const data = []
  const size = 1000000
  let i = 0
  let temp
  const c = function (a, b) {
    return a - b
  }
  for (i = 0; i < size; i++) {
    temp = Math.random() * Number.MAX_SAFE_INTEGER
    data.push(temp)
  }
  introsort(data, c)
  let faulty = false
  for (i = 1; i < size; i++) {
    if (data[i] < data[i - 1]) {
      faulty = true
      break
    }
  }
  if (faulty) {
    return 'WRONG!!'
  } else {
    return 'RIGHT:)'
  }
}

/**
 * @example Demo run of the sort routine
 * using the default compare function and
 * comparing the results with Array.sort
 */
function demo2 () {
  const data = []
  const data2 = []
  const size = 1000000
  let i = 0
  let temp
  for (i = 0; i < size; i++) {
    temp = Math.random() * Number.MAX_SAFE_INTEGER
    data.push(temp)
    data2.push(temp)
  }
  introsort(data)
  data2.sort()
  let faulty = false
  for (i = 1; i < size; i++) {
    if (data[i] !== data2[i]) {
      faulty = true
      break
    }
  }
  if (faulty) {
    return 'WRONG Implemented Comparator!!'
  } else {
    return 'Comparator Works Fine:)'
  }
}

export { introsort, demo1, demo2 }