Wir lernen nun ein Sortierverfahren kennen, das im Falle einer bereits sortierten Liste schneller ist als Selection Sort. Intuitiv verfahren wir wie beim Aufnehmen einer Hand beim Kartenspiel: Neue Elemente werden der Reihe nach in eine bereits sortierte Teil-Liste eingefügt.
Zur Implementierung in Python durchlaufen wir die Elemente der Liste nacheinander in einer Zählschleife. Wie bei Selection Sort soll nach jedem Durchlauf der Schleife das Teil-Liste von Position 0 bis zur Zählvariable i sortiert sein. Diesmal erreichen wir dies, indem wir das Element an Position i rückwärts in den bereits sortierten Teil einfügen.
def insertion_sort(a):
for i in range(0, len(a)):
insert_backwards(a, i)
Die Prozedur insert_backwards verwendet eine bedingte Schleife, um das Element an der gegebenen Position position so lange mit seinem Vorgänger zu vertauschen, wie es kleiner ist als dieser.
def insert_backwards(a, pos):
while pos > 0 and a[pos] < a[pos-1]:
swap(a, pos, pos-1)
pos = pos - 1
Sobald das einzufügende Element nicht mehr kleiner ist als sein Vorgänger, wird die Schleife beendet. Wir brauchen es dann nicht mehr mit den davor stehenden Elementen zu vergleichen, da diese bereits sortiert sind, das einzufügende Element also nicht kleiner sein kann.
Das folgende Beispiel illustriert die Vertauschungen, die dieser Algorithmus durchführt: