Insertion Sort (Sortieren durch (direktes ) Einfügen):
(Beispiel: Einsortieren der Karten beim Kartenspiel)
Betrachte die Elemente eines nach dem anderen und füge jedes an seinen richtigen Platz zwischen den bereits betrachteten ein (wobei diese sortiert bleiben).
Das gerade betrachtete Element wird eingefügt, indem die größeren Elemente einfach um eine Position nach rechts bewegt werden und das Element dann auf dem frei gewordenen Platz eingefügt wird.
Für jedes i von 2 bis N werden die Elemente a [1] ,..., a [i] sortiert, indem a [ i ] an die entsprechende Stelle in der sortierten Liste von Elementen in a[1] ,..., a[i-1] gesetzt wird.