Wir lernen nun ein Sortierverfahren kennen, das im Falle eines bereits sortierten Arrays schneller ist als Selection Sort. Intuitiv verfahren wir wie beim Aufnehmen einer Hand beim Kartenspiel: Neue Elemente werden der Reihe nach in ein bereits sortiertes Teil-Array eingefügt.
Zur Implementierung in Python durchlaufen wir die Elemente des Arrays nacheinander in einer Zählschleife. Wie bei Selection Sort soll nach jedem Durchlauf der Schleife das Teil-Array 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: