JavaScript Sorting Algorithm: Binary Insertion sort

JavaScript Sorting Algorithm: Exercise-27 with Solution

From Wikipedia,
Binary insertion sort employs a binary search to determine the correct location to insert new elements, and therefore performs [log₂ n] comparisons in the worst case. When each element in the array is searched for and inserted this is O(n log n). The algorithm as a whole still has a running time of O(n2) on average because of the series of swaps required for each insertion.

Write a JavaScript program to sort a list of elements using the Binary Insertion sort algorithm.

Sample Data: Original Array: [3, 1, 8, 9, 5]
Sorted Array: [1, 3, 5, 8, 9]
Original Array: [2, 4, 1, 7, 6, 9, 5]
Sorted Array: [1, 2, 4, 5, 6, 7, 9]

Sample Solution:

JavaScript Code:

/** 
 * License:shorturl.at/FSX26
 * @param {Array} array Array of numbers.
 * @param {Number} key Value to be searched
 * @param {Number} start start index position of array
 * @param {Number} end end index position of array
 * @return {Number} Position of the key element
 */
function binarySearch (array, key, start, end) {
  if (start === end) {
    if (array[start] > key) {
      return start
    } else {
      return start + 1
    }
  }

  if (start > end) {
    return start
  }

  const mid = Math.floor((start + end) / 2)

  if (array[mid] < key) {
    return binarySearch(array, key, mid + 1, end)
  } else if (array[mid] > key) {
    return binarySearch(array, key, start, mid - 1)
  } else {
    return mid
  }
}

/**
 * Binary Insertion Sort
 *
 * @param {Array} list List to be sorted.
 * @return {Array} The sorted list.
 */
function binaryInsertionSort (array) {
  const totalLength = array.length
  for (let i = 1; i < totalLength; i += 1) {
    const key = array[i]
    const indexPosition = binarySearch(array, key, 0, i - 1)
    array.splice(i, 1)
    array.splice(indexPosition, 0, key)
  }
  return array
}
arr = [3, 1, 8, 9, 5]
console.log("Original Array: "+arr)
result = binaryInsertionSort(arr)
console.log("Sorted Array: "+result)
arr = [2,4,1,7,6,9,5]
console.log("Original Array: "+arr)
result = binaryInsertionSort(arr)
console.log("Sorted Array: "+result) 

Sample Output:

"Original Array: 3,1,8,9,5"
"Sorted Array: 1,3,5,8,9"
"Original Array: 2,4,1,7,6,9,5"
"Sorted Array: 1,2,4,5,6,7,9"
"Original Array: 3,1,8,9,5"
"Sorted Array: 1,3,5,8,9"
"Original Array: 2,4,1,7,6,9,5"
"Sorted Array: 1,2,4,5,6,7,9"

Flowchart:

Live Demo:

See the Pen searching-and-sorting-algorithm-exercise-27 by w3resource (@w3resource) on CodePen.

Improve this sample solution and post your code through Disqus

Previous: Alpha Numerical Sort.
Next: Cycle sort.