Insertion Sort

Sorting

avgO(n²)worstO(n²)spaceO(1)

A single element is already a sorted prefix

1 / 210

Code

function insertionSort(a: number[]) {  for (let i = 1; i < a.length; i++) {    const key = a[i];    let j = i - 1;    while (j >= 0 && a[j] > key) {      a[j + 1] = a[j];      j--;    }    a[j + 1] = key;  }  return a;}

procedure insertionSort(A)  for i ← 1 to n − 1 do    key ← A[i]    j ← i − 1    while j ≥ 0 and A[j] > key do      A[j + 1] ← A[j]      j ← j − 1    end while    A[j + 1] ← key  end for  return Aend procedure

Variables

n=20

Counters

comparisons: 0
shifts: 0

Size20

Distribution

Custom values2 to 150 whole numbers, each 1 to 999

seed 3

How it works

Grows a sorted prefix one element at a time: each new key is shifted left past every larger element until it reaches its place. It is very fast on nearly sorted input, which is why hybrid sorts use it for small runs.

Complexity

Best: O(n)
Average: O(n²)
Worst: O(n²)
Space: O(1)
Stable: Yes
In place: Yes

Insertion Sort

How it works

Complexity

Search algorithms