Einfügen

Die Daten liegen wieder in einer Reihung vor. Eine Markierung trennt den sortierten Teil (links) vom unsortierten Teil (ratet mal wo!). Es wird immer der erste noch nicht einsortierte Wert markiert. Der so markierte Wert wird nun aus der Reihung herausgenommen und die Markierung eins nach rechts verschoben. Nun wird von links im sortierten Bereich die Stelle gesucht, an der der herausgenommene Wert eingefügt werden muss. Die nach rechts folgenden Werte müssen der Reihe nach um eine Stelle nach rechts verschoben werden. Dies kann von rechts oder von links geschehen. Danach wird auf die gleiche Weise der nächste Wert eingefügt, bis alle Werte neu eingefügt sind.

Ein Beispiel (Seite 2 der Präsentation): PDF-Datei zum Angucken und die OOo-Präsentation zum Bearbeiten.