Verfahren

Das Sortieren durch Einfügen ist ein intuitives und elementare Verfahren:

• Man teilt die zu sortierende Folge f mit N Elementen in eine bereits sortierte Teilfolge f[0] bis f[s-1] und in eine unsortierte Teilfolge f[s] bis f[n].
  • Zu Beginn ist die sortierte Teilfolge leer.
  • Der Beginn der unsortierten Folge f[s] wird die Sortiergrenze genannt.
• Man setzt eine Sortiergrenze hinter der bereits durch Zufall sortierte Teilfolge f[1] bis f[s-1]
• Vergleiche f[s] mit f[s-1] und vertausche die beiden Elemente falls f[s]<f[s-1]
  • Führe weitere Vergleiche und absteigende Vertauschungen durch bis man ein f[s-j] gefunden hat für das gilt f[s-j-1]<f[s-j]
• Erhöhe die Sortiergrenze von f[i] auf f[i+1] und wiederhole die Vergleichs- und Vertauschungsschritte wie im vorhergehenden Schritt beschrieben.
• Die Folge ist sortiert wenn die Sortiergrenze das Ende des Folge erreicht hat.

Beispiel

Gegeben sei ein Feld mit sieben Elementen. Die ersten beiden Elemente sind bereits sortiert und die Sortiergrenze kann daher auf die Index drei erhöht werden:

Auch das Einfügen des dritten Werts 35 erfordert keine Vertauschungen. Die Zahl 28 wird dann mit einer Vertauschung von Index 4 auf Index 3 einsortiert:

Die Sortiergrenze wird auf den Index 6 angehoben.

Die Zahl 19 auf Position 6 wird mot 3 Vertauschungen auf Index 3 bewegt.

Die Zahl 39 auf Index 7 muss nicht bewegt werden, das sie sich bereits auf der richtigen Position befindet.

Aufwand

Das Sortieren durch Einfügen braucht im günstigsten Fall nur N-1 Vergleiche für eine bereits sortierte Folge. Im ungünstigsten Fall (fallend sortiert) ist aber ein quadratisches Aufwand nötig.

Das gleiche gilt für die Vertauschungen. Hier müssen im ungünstigsten Fall Vertauschungen in einer quadratischen Größenordnung durchgeführt werden.