Sorting algorithms: bubble sort, merge sort and insertion sort

OCR J277 Paper 2 tests sorting algorithms with trace tables, code interpretation and comparison questions. You need to be able to trace each algorithm step by step AND compare their efficiency.

Bubble sort

Method

1. Compare each adjacent pair of elements.
2. If left > right: swap them.
3. Repeat for the whole list — this is one pass.
4. After each pass, the largest unsorted element "bubbles" to its correct position at the end.
5. Repeat for (n−1) passes. Stop early if a pass makes no swaps (list is sorted).

Worked example

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

Pass 1: [3,5,8,1,4] → [3,5,8,1,4] → [3,5,1,8,4] → [3,5,1,4,8] (8 in place) Pass 2: [3,5,1,4,8] → [3,1,5,4,8] → [3,1,4,5,8] (5 in place) Pass 3: [1,3,4,5,8] (already sorted after comparisons with no swaps)

Efficiency

• Worst case: O(n²) comparisons — suitable only for small lists.
• Best case: O(n) if the list is already sorted (one pass with no swaps).
• Simple to understand and code; very inefficient for large lists.

Insertion sort

Method

1. Start with the second element.
2. Compare it to elements to its left; insert it into the correct position.
3. Elements larger than the current element are shifted right.
4. Move to the next element and repeat.

Worked example

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

Step 1 (item=3): 3<5 → [3, 5, 8, 1, 4] Step 2 (item=8): 8>5 → no move: [3, 5, 8, 1, 4] Step 3 (item=1): 1<8, 1<5, 1<3 → [1, 3, 5, 8, 4] Step 4 (item=4): 4<8, 4<5, 4>3 → [1, 3, 4, 5, 8]

Efficiency

• Worst case: O(n²) — like bubble sort.
• Best case: O(n) if already sorted.
• Works well for small or nearly sorted lists; builds the sorted portion incrementally.

Merge sort

Method (divide and conquer)

1. Divide: repeatedly split the list in half until each sub-list has 1 element.
2. Merge: merge pairs of sub-lists back together in sorted order.

Worked example

[5, 3, 8, 1] → [5,3] [8,1] → [5] [3] [8] [1] Merge: [3,5] [1,8] → [1,3,5,8]

Efficiency

• Worst case: O(n log n) — much better than O(n²) for large lists.
• Best case: O(n log n) — consistently efficient.
• More complex to implement; uses more memory (for sub-lists); best for large lists.

Comparison table

Feature	Bubble sort	Insertion sort	Merge sort
Worst case	O(n²)	O(n²)	O(n log n)
Best case	O(n)	O(n)	O(n log n)
Good for small lists?	Yes	Yes (better than bubble)	No (overhead)
Good for large lists?	No	No	Yes
Memory usage	In-place	In-place	Extra memory needed

Common OCR exam mistakes

1. Forgetting that after each bubble sort pass, the last n−pass elements are already sorted — you don't need to compare them again.
2. Confusing merge sort's divide and merge phases — divide splits until 1 element; merge builds back up.
3. Stating "merge sort is always best" — for very small lists the overhead makes insertion sort or bubble sort practical choices.
4. Trace errors: on insertion sort, elements are shifted right (not swapped) to make room.