Insertionsort ({EnS|insertion} ‚Einfügen‘ und {EnS|sort} ‚sortieren‘) ist ein einfaches stabiles Sortierverfahren. Es ist einfach zu implementieren, effizient bei (ziemlich) kleinen Eingabemengen, effizient bei Eingabemengen, die schon vorsortiert sind, stabil (d. h. die Reihenfolge von Elementen mit gleichem Schlüsselwert bleibt unverä...