Insertion sort is een eenvoudig sorteeralgoritme dat werkt door telkens één element uit de ongesorteerde sectie van de lijst te nemen en het op de juiste positie in de gesorteerde sectie van de lijst in te voegen. Het begint met een gesorteerde sectie van één element (het eerste element van de lijst) en voegt vervolgens één voor één de overige elementen toe aan de gesorteerde sectie, waarbij de elementen op de juiste plaats worden ingevoegd. Via deze link krijg je een visuele voorstelling van het insertion sort algoritme.

Hier is een stapsgewijze uitleg van het insertion sort algoritme:

1. Begin met het beschouwen van het tweede element van de lijst.
2. Vergelijk dit element met het eerste element. Indien nodig, verwissel ze zodat de eerste twee elementen gesorteerd zijn.
3. Beschouw het derde element van de lijst en voeg dit in de gesorteerde sectie in door het te vergelijken met de elementen in de gesorteerde sectie van rechts naar links en deze te verschuiven totdat het juiste positie vindt.
4. Herhaal dit proces totdat alle elementen op hun juiste plaats staan.

Schrijf een functie insertionsort met een lijst van getallen als parameter die een gesorteerde lijst als returnwaarde heeft.

>>> insertionsort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]
>>> insertionsort([73, 41, 74, 72, 8, 10, 57, 84, 68, 21])
[8, 10, 21, 41, 57, 68, 72, 73, 74, 84]