Insertionsort

Insertionsort (auch Einfügesortieren, ‚Einfügen‘ und engl. ‚sortieren‘) ist ein einfaches stabiles Sortierverfahren (d. h. die Reihenfolge von Elementen mit gleichem Schlüsselwert bleibt unverändert). Es ist leicht zu implementieren, effizient bei kleinen oder bereits teilweise sortierten Eingabemengen. Außerdem benötigt Insertionsort keinen zusätzlichen Speicherplatz, da der Algorithmus in-place arbeitet.