Redigerer Sorteringsalgoritme (avsnitt)

===Skallsortering ===
Skallsortering (''shell sort'') er en forbedret variant av innstikksortering. Isteden for at algoritmen går fra ene siden sorterer den i "gap". Den kan for eksempel begynne med gap som er like store som halve datasettet, dette gir to operasjoner i første runde. Algoritmen sorterer det første tallet, tallet i midten og det siste tallet slik at de står riktig i forhold til hverandre. I neste runde kan den bruke gap på en fjerdedel av datasettet (fire operasjoner). Slik fortsetter den mens gapene blir mindre og mindre. Til slutt tar algoritmen alle tallene, men da er datasettet stort sett sortert. Med denne metoden flytter feilplasserte tall seg raskere gjennom datasettet enn ved tradisjonell innstikksortering. Algoritmen kan i verste fall bruke kvadratisk tid hvis tallene i data settet allerede er organisert slik at annen hvert tall er stort og annen hvert er lite. Dette kan imidlertid forhindres hvis man deler inn i gap ut fra andre systemer, f.eks. [[Fibonacci-tall]]ene, <math>2^k-1</math> eller andre tallsekvenser. Algoritmen ble beskrevet av Donald Shell i 1959.<ref>{{cite journal |last=Shell |first=D.L. |title=A high-speed sorting procedure |journal=Communications of the ACM |volume=2 |issue=7 |year=1959 |pages=30–32 |doi=10.1145/368370.368387}}</ref>