Insertion Sort

Vergleichsbasiert

Baut das sortierte Array Element für Element auf, indem jedes neue Element an der richtigen Position unter den bereits sortierten Elementen eingefügt wird.

Live-Visualisierung

Komplexität

Bester Fall	O(n)
Durchschnitt	O(n²)
Schlechtester Fall	O(n²)
Speicherkomplexität	O(1)
Stabiles Sortieren	Ja
In-Place	Ja

Legende

O(1): Konstant: Egal wie viele Elemente — der Aufwand bleibt gleich.
O(n): Linear: Doppelt so viele Elemente → doppelt so viel Aufwand.
O(n log n): Quasi-Linear: Wenig schlechter als linear — der Goldstandard für Sortieren.
O(n²): Quadratisch: 10× mehr Elemente → 100× mehr Aufwand. Langsam bei großen Listen.
Stabil: Stabile Sortierung: Gleiche Werte behalten ihre ursprüngliche Reihenfolge zueinander.
In-Place: In-Place: Sortiert direkt im vorhandenen Speicher, ohne eine Kopie der Liste anzulegen.
Vergleichsbasiert: Vergleichsbasiert: Der Algorithmus entscheidet nur durch „ist A kleiner als B?" — funktioniert mit beliebigen Werten.
Nicht-Vergleichsbasiert: Nicht-Vergleichsbasiert: Nutzt die Struktur der Zahlen selbst (z. B. Ziffern) — kann dadurch schneller als O(n log n) sein.

Implementierung

TypeScript-Implementierung — direkt kopierbereit.

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

Wie es funktioniert

Insertion Sort ist vergleichbar mit dem Sortieren von Spielkarten in der Hand. Eine Karte nach der anderen wird aufgenommen und nach links an die richtige Position zwischen den bereits sortierten Karten geschoben. Die linke Seite ist stets sortiert; sie wächst pro Schritt um ein Element.

Warum er wichtig ist: Insertion Sort ist bei nahezu sortierten Daten extrem schnell (O(n) Vergleiche), adaptiv (die Leistung verbessert sich mit vorhandener Ordnung) und hat sehr geringen Overhead. Deshalb wird er für kleine Arrays bevorzugt — TimSort (verwendet in Python und Java) nutzt ihn für Teilarrays unterhalb einer Schwelle (~32–64 Elemente).

Wann verwenden: Kleine Arrays (< 20 Elemente), nahezu sortierte Eingaben oder als Basisfall in hybriden Algorithmen.

Vergleiche Insertion Sort direkt mit einem anderen Algorithmus

Code vergleichen →

Selection Sort Merge Sort