Shellsortering

Shellsortering er en form for på-stedet sammenligningsortering som kan betraktes som en generalisering av enten boblesortering eller innstikksortering. Metoden starter ved å sortere par av elementer som er langt fra hverandre, og deretter progressivt redusere gapet mellom de sammenlignede elementer. Ved å begynne på elementer som er langt fra hverandre, kan den flytte enkelte elementer som er utenfor rekkefølge inn i sin rette posisjon raskere enn en enkel naboutveksling. Donald Shell publiserte den første versjonen i 1959. Kjøretiden til algoritmen er svært avhengig av gapsekvensen den bruker. For mange praktiske verdier, er deres tidskompleksitet et åpent problem.