Insertion Sort

Insertion sort is a simple sorting algorithm that builds the sorted list one item at a time. It works similarly to the way you might sort a hand of playing cards — you pick up each card and insert it into its correct position among the cards you have already sorted.

---

How Insertion Sort Works

1. Start with the second element in the list (the first element is considered already sorted).
2. Compare this element with the elements to its left.
3. Shift all elements that are greater than the current element one position to the right.
4. Insert the current element into its correct position.
5. Move to the next element and repeat steps 2–4.
6. Continue until every element has been inserted into its correct position.

---

Pseudocode for Insertion Sort

FUNCTION insertionSort(list)
    FOR i = 1 TO LENGTH(list) - 1
        current = list[i]
        j = i - 1
        WHILE j >= 0 AND list[j] > current
            list[j + 1] = list[j]
            j = j - 1
        ENDWHILE
        list[j + 1] = current
    NEXT i
    RETURN list
ENDFUNCTION

---

Worked Example

Sort the list: [5, 3, 8, 1, 2]