TimSort.js

/**
 *  @function Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort,
 *  designed to perform well on many kinds of real-world data.
 *  It was implemented by Tim Peters in 2002 for use in the Python programming language.
 *  It is also used to sort arrays of non-primitive type in Java SE 7,
 *  on the Android platform, in GNU Octave, on V8, Swift and Rust.
 *  1) It sorts small partitions using Insertion Sort.
 *  2) Merges the partition using Merge Sort.
 *  @see [Timsort](https://en.wikipedia.org/wiki/Timsort)
 *  @param {Array} array
 */

const Timsort = (array) => {
  // Default size of a partition
  const RUN = 32
  const n = array.length
  // Sorting the partitions using Insertion Sort
  for (let i = 0; i < n; i += RUN) {
    InsertionSort(array, i, Math.min(i + RUN - 1, n - 1))
  }
  for (let size = RUN; size < n; size *= 2) {
    for (let left = 0; left < n; left += 2 * size) {
      const mid = left + size - 1
      const right = Math.min(left + 2 * size - 1, n - 1)
      Merge(array, left, mid, right)
    }
  }
  return array
}

/**
 * @function performs insertion sort on the partition
 * @param {Array} array array to be sorted
 * @param {Number} left left index of partition
 * @param {Number} right right index of partition
 */

const InsertionSort = (array, left, right) => {
  for (let i = left + 1; i <= right; i++) {
    const key = array[i]
    let j = i - 1
    while (j >= left && array[j] > key) {
      array[j + 1] = array[j]
      j--
    }
    array[j + 1] = key
  }
}

/**
 * @function merges two sorted partitions
 * @param {Array} array array to be sorted
 * @param {Number} left left index of partition
 * @param {Number} mid mid index of partition
 * @param {Number} right right index of partition
 */

const Merge = (array, left, mid, right) => {
  if (mid >= right) return
  const len1 = mid - left + 1
  const len2 = right - mid
  const larr = Array(len1)
  const rarr = Array(len2)
  for (let i = 0; i < len1; i++) {
    larr[i] = array[left + i]
  }
  for (let i = 0; i < len2; i++) {
    rarr[i] = array[mid + 1 + i]
  }
  let i = 0
  let j = 0
  let k = left
  while (i < larr.length && j < rarr.length) {
    if (larr[i] < rarr[j]) {
      array[k++] = larr[i++]
    } else {
      array[k++] = rarr[j++]
    }
  }
  while (i < larr.length) {
    array[k++] = larr[i++]
  }
  while (j < rarr.length) {
    array[k++] = rarr[j++]
  }
}

/**
 * @example Test of Timsort functions.
 * Data is randomly generated.
 * Return "RIGHT" if it works as expected,
 * otherwise "FAULTY"
 */
const demo = () => {
  const size = 1000000
  const data = Array(size)
  for (let i = 0; i < size; i++) {
    data[i] = Math.random() * Number.MAX_SAFE_INTEGER
  }
  const isSorted = function (array) {
    const n = array.length
    for (let i = 0; i < n - 1; i++) {
      if (array[i] > array[i + 1]) return false
    }
    return true
  }
  Timsort(data)
  if (isSorted(data)) {
    return 'RIGHT'
  } else {
    return 'FAULTY'
  }
}

export { Timsort, demo }