Big O Visualizer

Insertion Sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.

Complexity

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.

Algorithm

Below the implementation of Insertion Sort as used on this page.

1export default class InsertionSort extends Algorithm {
2  name = "Insertion Sort"
3  timeComplexityBest = Complexities.linear
4  timeComplexityAverage = Complexities.quadratic
5  timeComplexityWorst = Complexities.quadratic
6
7  execute(array: number[]): void {
8    const len = array.length
9    for (let i = 1; i < len; i++) {
10      const key = array[i]
11      let j = i - 1
12      while (j >= 0 && array[j] > key) {
13        array[j + 1] = array[j]
14        j -= 1
15        this.incrementOpCounter()
16      }
17      array[j + 1] = key
18      this.incrementOpCounter()
19    }
20  }
21}