Informatik

Wie funktioniert Insertion Sort?

Insertion Sort baut links einen sortierten Bereich auf und fügt jedes neue Element an der richtigen Position ein.

Worst Case: $O(n^2)$. Best Case bei bereits sortierter Eingabe: $O(n)$. Stabil und in-place.