Man har olika siffror (element) som kommer att stoppar i ett array element efter element på dess rätta ställe i den dittils sorterade mängden. Eftersom varje instättning kräver att man flyttar all data som ligger för tidigt ett snäpp så får man en tidskomplexitet på O(n^2).

Om man däremot vet att inget element ligger mer än ett fåtal positioner från sin rätta plats så är algoritmen linjär i tiden (O(n)).

Det gör algoritmen till ett bra val för slutfasten när andra algoritmer grovsorteras.

Algoritmen (pseudokod)

* n - Antalet element

* A - array med saker att sortera. Indexar från A[0] till A[n-1]

for i from 1 to n-1 do
j := i
x := A[i]

while j >= 1 and A[j-l] > x
j := j-1

A[j] = x

/ Är det någon som har några tips för at jag ska lösa den. Har suttit i någon timme nu och funderat men behöver lite hjälp.

Hjälp till om ni förstår er på detta! Skriv inte onödiga kommentarer.

Tack på förhand!