🃏 Insertion Sort

Funktioniert wie das Sortieren von Spielkarten in der Hand. Ein Element wird genommen und an der passenden Stelle in den bereits sortierten Teil eingefügt.

Complexity

Zeit:O(n²)

Platz:O(1)

Code Snippet

for (let i = 1; i < n; i++) {
  let key = arr[i];
  let j = i - 1;
  while (j >= 0 && arr[j] > key) {
    arr[j + 1] = arr[j];
    j--;
  }
  arr[j + 1] = key;
}

Speed