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.

The insertion loop in flowchart form:

graph TD
    A["Start: i = 1"] --> B{"i less than n?"}
    B -->|No| C["Done — list sorted"]
    B -->|Yes| D["current = list[i], j = i - 1"]
    D --> E{"j >= 0 AND list[j] > current?"}
    E -->|Yes| F["Shift: list[j+1] = list[j]"]
    F --> G["j = j - 1"]
    G --> E
    E -->|No| H["Insert: list[j+1] = current"]
    H --> I["i = i + 1"]
    I --> B

---

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]

We treat the first element (5) as already sorted. The bold section is the sorted portion.

Step 1: Insert 3

Current = 3. Compare with 5. 3 < 5, so shift 5 right and insert 3.

Sorted	Unsorted
[3, 5]	[8, 1, 2]

Step 2: Insert 8

Current = 8. Compare with 5. 8 > 5, so no shifting needed. Insert 8 at the end.

Sorted	Unsorted
[3, 5, 8]	[1, 2]

Step 3: Insert 1

Current = 1. Compare with 8 (shift), 5 (shift), 3 (shift). Insert 1 at the beginning.

Sorted	Unsorted
[1, 3, 5, 8]	[2]

Step 4: Insert 2

Current = 2. Compare with 8 (shift), 5 (shift), 3 (shift). 2 > 1, so insert after 1.

Sorted	Unsorted
[1, 2, 3, 5, 8]	[]

Final result: [1, 2, 3, 5, 8]

---

Trace Table for Insertion Sort

A trace table showing the state of the list after each insertion:

Pass	Current Element	List After Insertion
1	3	[3, 5, 8, 1, 2]
2	8	[3, 5, 8, 1, 2]
3	1	[1, 3, 5, 8, 2]
4	2	[1, 2, 3, 5, 8]

---

Efficiency of Insertion Sort

Case	Time Complexity	Explanation
Best case	O(n)	List is already sorted — each element only needs one comparison
Worst case	O(n²)	List is in reverse order — maximum shifts needed
Average case	O(n²)	Roughly n²/4 comparisons and shifts

---

Advantages of Insertion Sort

• Simple to understand and implement
• Very efficient for small datasets or nearly sorted data
• Best case O(n) — excellent when data is already mostly sorted
• In-place sorting — requires no extra memory (space complexity O(1))
• Stable sort — equal elements maintain their relative order
• Adaptive — works faster on partially sorted data

Disadvantages of Insertion Sort

• O(n²) worst case — slow for large, unsorted datasets
• Not suitable for large datasets compared to merge sort

---

Comparing Sorting Algorithms

Feature	Bubble Sort	Insertion Sort	Merge Sort
Best case	O(n)	O(n)	O(n log n)
Worst case	O(n²)	O(n²)	O(n log n)
Average case	O(n²)	O(n²)	O(n log n)
Space	O(1)	O(1)	O(n)
Stable	Yes	Yes	Yes
Best for	Small/nearly sorted	Small/nearly sorted	Large datasets

Exam Tip: Insertion sort is often compared to bubble sort in exams. Key difference: insertion sort typically makes fewer comparisons and is generally faster in practice for nearly sorted data. Both are O(n²) worst case but insertion sort is usually preferred for small datasets.

---

Key Points

• Insertion sort builds the sorted list one element at a time.
• It inserts each element into its correct position within the already-sorted portion.
• Time complexity: O(n) best case, O(n²) worst case.
• Space complexity: O(1) — sorts in place.
• Efficient for small or nearly sorted datasets.

---

Extended Worked Examples

Worked Example A: Full Trace on [7, 2, 5, 1, 8, 3]

We begin with index 0 (value 7) treated as the sorted region of size 1.

Pass 1 — insert list[1] = 2

current = 2, j = 0. Compare list[0] (7) with 2: 7 > 2, shift right.

j	list[j]	Comparison	list state
0	7	7 > 2, shift	[7, 7, 5, 1, 8, 3]
-1	—	loop exits	insert 2 at index 0 → [2, 7, 5, 1, 8, 3]

Pass 2 — insert list[2] = 5

current = 5, j = 1.

j	list[j]	Comparison	list state
1	7	7 > 5, shift	[2, 7, 7, 1, 8, 3]
0	2	2 < 5, stop	insert 5 at index 1 → [2, 5, 7, 1, 8, 3]

Pass 3 — insert list[3] = 1

current = 1, j = 2.