Insertion Sort

Builds a sorted array one element at a time by inserting each into its correct position.

0 elements

SpdSize50

>Ready — Insertion Sort

Code

for (let i = 1; i < length; i++) {
  let j = i;
  while (j > 0 && compare(j - 1, j)) {
    swap(j - 1, j);
    j--;
  }
}

for (let i = 1; i < length; i++) {
  let j = i;
  while (j > 0 && compare(j - 1, j)) {
    swap(j - 1, j);
    j--;
  }
}

Analysis

BEST O(n)

AVG O(n²)

WORST O(n²)

SPACE O(1)

STABLE

Insertion Sort builds a sorted portion from left to right. For each new element, it shifts larger sorted elements right to make room, then inserts the element in place. Efficient for small or nearly-sorted data.

Edit in playground→