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 }