Analysieren Sie die Laufzeit des Insertion Sort Algorithmus experimentell analog zu Selection Sort. Testen Sie den Algorithmus außerdem mit umgekehrt sortieren Arrays unterschiedlicher Größe und beschreiben Sie Ihre Beobachtungen. Erzeugen Sie solche Arrays mit Hilfe einer selbst definierten Funktion descending. Zum Beispiel soll der Aufruf descending(5) als Ergebnis das Array [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 das Array 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.