Analysieren Sie die Laufzeit des Insertion Sort Algorithmus experimentell analog zu Selection Sort. Testen Sie den Algorithmus außerdem mit umgekehrt sortieren Listen unterschiedlicher Größe und beschreiben Sie Ihre Beobachtungen. Erzeugen Sie solche Listen mit Hilfe einer selbst definierten Funktion descending. Zum Beispiel soll der Aufruf descending(5) als Ergebnis die Liste [5,4,3,2,1] liefern.
Alternativ zu der gezeigten Implementierung sollen Sie Insertion Sort nun rekursiv implementieren. Definieren Sie dazu eine rekursive Prozedur ins_sort, die zwei Argumente a und to erwartet und die Liste a bis zur Position to sortiert.
Statt einer Zählschleife zu verwenden, deren Invariante besagt, dass ein Anfangsstück bereits sortiert ist, können Sie mit Hilfe eines rekursiven Aufrufs explizit Anfangsstücke sortieren, bevor Sie Elemente mit Hilfe der Prozedur insert_backwards rückwärts einfügen.