Insertion Sort

Insertion Sort baut eine sortierte Präfix auf und fügt das nächste Element an der richtigen Stelle ein (Verschieben).

Best case bei schon sortierten Daten: $O(n)$. Worst case $O(n^{2})$. Stabil und gut für kleine oder fast sortierte Arrays.

Fast sortierte Daten, kleine n, innere Schleife von Hybrid-Sortierern (TimSort nutzt Insertions auf Runs). Deshalb bleibt Insertion praktisch relevant.

Vertiefung

Insertion Sort hält einen bereits sortierten Präfix. Das nächste Element wird zwischengespeichert, grössere Präfixelemente werden nach rechts verschoben, und die entstandene Lücke nimmt das Element auf. Nach jeder Runde ist der Präfix um eine Position gewachsen und weiterhin sortiert.

Die Arbeit entspricht eng der Zahl inverser Paare, also der Paare, die relativ zur Zielordnung vertauscht stehen. Fast sortierte Daten erzeugen deshalb wenige Verschiebungen. Stark umgekehrte Ordnung führt dagegen zu einer langen Verschiebekette pro Runde.

Schwierigkeitsstufen

1. Ein Element in einen sortierten Präfix einfügen.
2. Verschiebungen mit der Zahl der Inversionen verbinden.
3. Die Stabilität durch die genaue Vergleichsbedingung erhalten.

Fallstricke

Wird bei Gleichheit ebenfalls verschoben, kann sich die Reihenfolge gleichwertiger Datensätze ändern. Häufig geht auch das zwischengespeicherte Element verloren, wenn direkt im Array überschrieben wird.