Een array van 10 elementen wordt met insertion sort oplopend gesorteerd. Elk element vanaf het tweede wordt eruit gehaald en vergeleken met de elementen links ervan, te beginnen bij de linkerbuur, tot een element kleiner dan of gelijk aan de waarde is gevonden of het begin is bereikt. Hoeveel vergelijkingen zijn er nodig als de array al oplopend staat, en als hij aflopend staat?

Antwoord: C. 9 en 45

Staat de array al oplopend, dan heeft elk element maar één vergelijking met zijn linkerbuur nodig, dus de 9 elementen vragen in totaal 9 vergelijkingen. Staat hij aflopend, dan wordt het als i-de uitgehaalde element vergeleken met alle i elementen links ervan, wat 1 + 2 + … + 9 = 45 geeft. Insertion sort hangt dus sterk af van de invoer, met O(n) in het beste en O(n²) in het slechtste geval, en is zeer snel op bijna gesorteerde gegevens. Shellsort benut dit door eerst insertion sort uit te voeren op elementen die een afstand uit elkaar liggen, en ook Timsort gebruikt insertion sort voor korte stukken.