Insertion Sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.
Insertion Sort has a linear best-case time complexity, which can be tested using a list of numbers that's already sorted.
Insertion Sort has a quadratic average-case time complexity, which can be tested using a random list of numbers.
Insertion Sort has a quadratic worst-case time complexity, which can be tested using a reversed list of numbers.
Note that the number of operations required is higher (roughly double) when compared to the average-case.
Below the implementation of Insertion Sort as used on this page.
1export default class InsertionSort extends Algorithm {2 name = "Insertion Sort"3 timeComplexityBest = Complexities.linear4 timeComplexityAverage = Complexities.quadratic5 timeComplexityWorst = Complexities.quadratic67 execute(array: number[]): void {8 const len = array.length9 for (let i = 1; i < len; i++) {10 const key = array[i]11 let j = i - 112 while (j >= 0 && array[j] > key) {13 array[j + 1] = array[j]14 j -= 115 this.incrementOpCounter()16 }17 array[j + 1] = key18 this.incrementOpCounter()19 }20 }21}