Insättningssortering

Insättningssortering, eller insertion sort på svenska, är en enkel sorteringsalgoritm som bygger upp en sorterad sektion av listan stegvis. Man börjar med det första elementet som en sorterad del och går sedan igenom resten av listan, och för varje nytt element sätter man in det på rätt plats i den redan sorterade delen.

Algoritmen arbetar genom att upprepa följande steg: välj det aktuella elementet, kalla det nyckeln, jämför nyckeln med elementen i den sorterade delen som föregår den och flytta uppåt de element som är större än nyckeln. När platsen hittas sätts nyckeln där. På så sätt växer den sorterade delen med ett element i taget, tills hela listan är sorterad.

Egenskaper och prestanda: insättningssortering är stabil, vilket innebär att lika element behåller sin ursprungliga ordning. Den är in-place och kräver endast O(1) extra minne. Genomsnittlig och värsta tidskomplexitet är O(n^2), medan bästa fall, när listan redan är sorterad, är O(n). Antalet flyttningar och jämförelser är relativt starkt beroende på hur data är ordnade.

Användning: på grund av sin enkelhet och låga marginalkostnad vid små listor eller nästan sorterade data används insättningssortering ofta i undervisning, lättviktiga applikationer och som grundkomponent i vissa hybrid-sorter. En variant är binary insertion sort, som använder binär sökning för att hitta insatspositionen men fortfarande har O(n^2) tidskomplexitet.