Sorting Algorithms: Bubble Sort, Merge Sort, and Insertion Sort

Sorting algorithms arrange data into a specific order — usually ascending (smallest to largest) or descending (largest to smallest). In GCSE Computer Science, you must understand three sorting algorithms: bubble sort, merge sort, and insertion sort. You need to know how each works, trace through examples, and compare their efficiency.

---

Bubble Sort

Bubble sort works by repeatedly comparing adjacent pairs of items and swapping them if they are in the wrong order. The largest unsorted value "bubbles" to the end of the list after each pass. The algorithm repeats until no swaps are made in a complete pass.

How Bubble Sort Works

1. Start at the beginning of the list
2. Compare the first two adjacent items
3. If they are in the wrong order, swap them
4. Move to the next pair and repeat
5. After one complete pass, the largest item is in its correct position
6. Repeat the process for the remaining unsorted items
7. Stop when a complete pass is made with no swaps (the list is sorted)

Pseudocode for Bubble Sort

PROCEDURE bubbleSort(list)
    n ← LENGTH(list)
    FOR i ← 0 TO n - 2
        swapped ← FALSE
        FOR j ← 0 TO n - 2 - i
            IF list[j] > list[j + 1] THEN
                temp ← list[j]
                list[j] ← list[j + 1]
                list[j + 1] ← temp
                swapped ← TRUE
            END IF
        END FOR
        IF swapped = FALSE THEN
            RETURN     // List is sorted, exit early
        END IF
    END FOR
END PROCEDURE

Trace Example

List: [5, 3, 8, 1, 2]

Pass 1:

• Compare 5, 3 → Swap → [3, 5, 8, 1, 2]
• Compare 5, 8 → No swap → [3, 5, 8, 1, 2]
• Compare 8, 1 → Swap → [3, 5, 1, 8, 2]
• Compare 8, 2 → Swap → [3, 5, 1, 2, 8]

Pass 2:

• Compare 3, 5 → No swap → [3, 5, 1, 2, 8]
• Compare 5, 1 → Swap → [3, 1, 5, 2, 8]
• Compare 5, 2 → Swap → [3, 1, 2, 5, 8]

Pass 3:

• Compare 3, 1 → Swap → [1, 3, 2, 5, 8]
• Compare 3, 2 → Swap → [1, 2, 3, 5, 8]

Pass 4:

• Compare 1, 2 → No swap → [1, 2, 3, 5, 8]
• No swaps made — list is sorted!

Properties of Bubble Sort

• Simple to understand and implement
• Inefficient for large datasets — worst case is O(n²) comparisons
• In-place — does not require extra memory (sorts within the original list)
• Can detect if already sorted — if no swaps in a pass, it can stop early

---

Merge Sort

Merge sort uses a divide-and-conquer approach. It works by repeatedly splitting the list in half until each sub-list contains a single item, then merging the sub-lists back together in the correct order.

How Merge Sort Works

1. If the list has one item (or is empty), it is already sorted — return it
2. Split the list into two halves
3. Recursively sort each half using merge sort
4. Merge the two sorted halves into a single sorted list

The Merge Process

When merging two sorted sub-lists:

1. Compare the first item of each sub-list
2. Take the smaller item and add it to the merged list
3. Repeat until all items from both sub-lists are in the merged list

Trace Example

List: [6, 3, 8, 1, 5, 2]

Split phase:

[6, 3, 8, 1, 5, 2]
      /          \
[6, 3, 8]    [1, 5, 2]
  /    \       /    \
[6]  [3, 8]  [1]  [5, 2]
      / \          / \
    [3] [8]      [5] [2]

Merge phase:

    [3] [8]      [5] [2]
      \ /          \ /
    [3, 8]      [2, 5]
  \    /       \    /
[3, 6, 8]    [1, 2, 5]
      \          /
[1, 2, 3, 5, 6, 8]

Pseudocode for Merge Sort

FUNCTION mergeSort(list)
    IF LENGTH(list) <= 1 THEN
        RETURN list
    END IF
    mid ← LENGTH(list) DIV 2
    left ← mergeSort(list[0..mid-1])
    right ← mergeSort(list[mid..end])
    RETURN merge(left, right)
END FUNCTION

FUNCTION merge(left, right)
    result ← []
    WHILE LENGTH(left) > 0 AND LENGTH(right) > 0
        IF left[0] <= right[0] THEN
            APPEND left[0] TO result
            REMOVE first item from left
        ELSE
            APPEND right[0] TO result
            REMOVE first item from right
        END IF
    END WHILE
    APPEND remaining items from left TO result
    APPEND remaining items from right TO result
    RETURN result
END FUNCTION

Properties of Merge Sort

• Efficient — always O(n log n) comparisons, even in the worst case
• Consistent — performance does not depend on the initial order of the data
• Not in-place — requires additional memory to store the sub-lists during merging
• Uses recursion — the function calls itself

---

Insertion Sort

Insertion sort works by building a sorted section of the list one item at a time. It takes each item from the unsorted section and inserts it into the correct position in the sorted section.

How Insertion Sort Works

1. The first item is considered already sorted
2. Take the next item from the unsorted section
3. Compare it with items in the sorted section, moving from right to left
4. Shift items in the sorted section to the right to make space
5. Insert the item in its correct position
6. Repeat until all items are in the sorted section

Pseudocode for Insertion Sort

PROCEDURE insertionSort(list)
    FOR i ← 1 TO LENGTH(list) - 1
        key ← list[i]
        j ← i - 1
        WHILE j >= 0 AND list[j] > key
            list[j + 1] ← list[j]
            j ← j - 1
        END WHILE
        list[j + 1] ← key
    END FOR
END PROCEDURE

Trace Example

List: [5, 3, 8, 1, 2]

Pass	Key	Action	List After
1	3	3 < 5, insert before 5	[3, 5, 8, 1, 2]
2	8	8 > 5, stays in place	[3, 5, 8, 1, 2]
3	1	1 < 8, 1 < 5, 1 < 3, insert at start	[1, 3, 5, 8, 2]
4	2	2 < 8, 2 < 5, 2 < 3, 2 > 1, insert after 1	[1, 2, 3, 5, 8]

Properties of Insertion Sort

• Simple to implement
• Efficient for small or nearly sorted lists — best case is O(n) when the list is already sorted
• Inefficient for large unsorted lists — worst case is O(n²)
• In-place — does not require extra memory
• Adaptive — performs well when data is partially sorted

---

Comparing the Three Sorting Algorithms

Feature	Bubble Sort	Merge Sort	Insertion Sort
Best case	O(n) — already sorted	O(n log n)	O(n) — already sorted
Worst case	O(n²)	O(n log n)	O(n²)
Average case	O(n²)	O(n log n)	O(n²)
In-place?	Yes	No (needs extra memory)	Yes
Stable?	Yes	Yes	Yes
Best for	Small/nearly sorted lists	Large datasets	Small/nearly sorted lists

Exam Tip: Be ready to trace through each algorithm step by step. Merge sort questions often ask you to show the split and merge phases. Bubble sort questions often ask how many passes or swaps are needed. Insertion sort questions ask you to show the sorted section growing.

---

Summary