# Insertion Sort visualisieren: Karten einsortieren in O(n^2)

> Insertion Sort interaktiv: baut links einen sortierten Präfix auf und schiebt jedes neue Element an seinen Platz. Bestenfalls linear, sonst quadratisch, stabil.

Adresse: https://marckimmel.de/informatik/sortieralgorithmen/insertion-sort
English version: https://marckimmel.de/en/informatik/sortieralgorithmen/insertion-sort.md

Baut links eine sortierte Teilfolge auf und fügt jedes neue Element an die richtige Stelle ein.

Insertion Sort behandelt das Array wie einen Stapel Karten: links liegt der bereits sortierte Teil, rechts der unsortierte. In jedem Schritt nimmt der Algorithmus das erste unsortierte Element (den Key) und vergleicht es von rechts nach links mit allen Werten im sortierten Teil. Solange ein Wert größer als der Key ist, wird er um eine Position nach rechts geschoben. Sobald ein kleinerer Wert (oder der Anfang) erreicht ist, wird der Key in die entstandene Lücke gesetzt. Der sortierte Präfix wächst dadurch in jeder Iteration um eins. Im Best Case ist die Eingabe bereits sortiert und der innere Vergleich endet sofort, weshalb die Best-Case-Laufzeit linear ist (O(n)). Im Mittel und im Worst Case müssen pro Element bis zu i Werte verglichen und verschoben werden, was zu quadratischer Gesamtlaufzeit führt (O(n^2)). Insertion Sort arbeitet in-place und braucht nur konstant viel Zusatzspeicher (O(1)). Die Reihenfolge gleichwertiger Elemente bleibt erhalten, der Algorithmus ist also stabil.

Sehr stark bei kleinen Arrays mit weniger als rund 20 Elementen und bei nahezu sortierten Daten, wo die Laufzeit auf linear absinkt. Genau deshalb wechseln viele Hybrid-Sortierer wie Timsort intern auf Insertion Sort, sobald die rekursiven Teilbereiche klein genug sind.

## Weiter

- [Sortieralgorithmen](https://marckimmel.de/informatik/sortieralgorithmen.md)