Skip to content### Complexity

### Algorithm

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.

src/algorithms/insertion-sort.ts

`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}`