Skip to content

Big O Visualizer

Insertion Sort

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.

src/algorithms/insertion-sort.ts
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}