Ein Array mit 10 Elementen wird mit Insertionsort aufsteigend sortiert. Jedes Element ab dem zweiten wird herausgenommen und mit den Elementen links davon verglichen, beginnend beim linken Nachbarn, bis ein Element gefunden wird, das kleiner oder gleich ist, oder der Anfang erreicht ist. Wie viele Vergleiche sind nötig, wenn das Array bereits aufsteigend sortiert ist, und wie viele, wenn es absteigend sortiert ist?

Antwort: C. 9 und 45

Ist das Array bereits aufsteigend sortiert, braucht jedes Element nur einen Vergleich mit seinem linken Nachbarn, die 9 Elemente also insgesamt 9 Vergleiche. Ist es absteigend sortiert, wird das als i-tes herausgenommene Element mit allen i Elementen links davon verglichen, was 1 + 2 + … + 9 = 45 ergibt. Insertionsort hängt also stark von der Eingabe ab, mit O(n) im besten und O(n²) im schlechtesten Fall, und ist bei nahezu sortierten Daten sehr schnell. Shellsort nutzt das aus, indem es zuerst Insertionsort auf Elemente im Abstand einer Lücke anwendet, und auch Timsort verwendet Insertionsort für kurze Teilfolgen.