Write, trace and analyse bubble sort in pseudo-code
Write, trace and analyse insertion sort in pseudo-code
Explain the merge sort algorithm (divide and conquer) and trace a merge
Compare all three algorithms and justify algorithm selection for given scenarios
Bubble Sort
Bubble Sort
procedure bubbleSort(arr) for i ← 0 to len(arr)-2 for j ← 0 to len(arr)-2-i if arr[j] > arr[j+1] then temp ← arr[j] arr[j] ← arr[j+1] arr[j+1] ← temp endif next j next i endprocedure
Complexity: O(n²) worst/average case. Best case O(n) if list is already sorted (with optimised version checking for no swaps). Space: O(1) — in-place sort. Stable sort — equal elements maintain their relative order.
Bubble Sort Trace
Tracing Bubble Sort
Sort: [5, 2, 8, 1, 9]
Pass 1 (i=0)
j=0: 5>2 → swap → [2,5,8,1,9] j=1: 5<8 → no swap → [2,5,8,1,9] j=2: 8>1 → swap → [2,5,1,8,9] j=3: 8<9 → no swap → [2,5,1,8,9] 9 is now in correct position
procedure insertionSort(arr) for i ← 1 to len(arr)-1 key ← arr[i] j ← i - 1 while j ≥ 0 AND arr[j] > key arr[j+1] ← arr[j] j ← j - 1 endwhile arr[j+1] ← key next i endprocedure
Builds a sorted portion from left to right. Each element is "inserted" into its correct position in the sorted portion. O(n²) worst case; O(n) best case (nearly sorted data). Efficient for small n and nearly-sorted lists. Stable and in-place.
Merge sort divides the list in half recursively until single elements remain (base case), then merges pairs of sorted lists into larger sorted lists. Always O(n log n) — even worst case.
Time: O(n log n) — all cases Space: O(n) — requires extra array for merging Stable sort
Merge Step
Two sorted sub-arrays → one sorted array. Compare front elements; take smaller. Repeat until one sub-array empty; append remaining. O(n) per merge level.
Comparison
Sorting Algorithm Comparison
Bubble Sort
Time: O(n²) worst; O(n) best Space: O(1) Stable: yes Best for: teaching; tiny datasets Not used in practice for large n
Insertion Sort
Time: O(n²) worst; O(n) best Space: O(1) Stable: yes Best for: nearly-sorted or small datasets. Good for online sorting (data arrives one item at a time)
Merge Sort
Time: O(n log n) always Space: O(n) extra Stable: yes Best for: large datasets; guaranteed performance; when extra memory available. Used in Python's Timsort (hybrid merge/insertion).
Exam Practice
OCR H446 Style · 5 marks
Show the state of the list [9, 3, 7, 1, 5] after each pass of bubble sort, and explain why bubble sort has a worst-case time complexity of O(n²).
O(n²) because there are n-1 passes (outer loop), and each pass makes up to n-1-i comparisons (inner loop). Total comparisons = (n-1)+(n-2)+…+1 = n(n-1)/2. This is a polynomial in n² — so worst case is O(n²).
Common Mistakes
Don't Lose Marks
!
Not showing the full list state after each pass in a bubble sort trace — show ALL elements, not just the ones that moved. Mark schemes check each position. If you only show the swapped pair and omit unchanged elements, you will lose marks.
!
Saying merge sort is always faster than bubble sort — this is true for large n, but for very small lists (n < 10), insertion sort and bubble sort can outperform merge sort because they have no recursive call overhead. Qualify your answer with "for large n".
!
Describing merge sort without mentioning the merge step — "divide the list in half recursively" is only half the answer. The combine/merge step (comparing elements from two sorted sub-arrays and building the sorted result) is what makes merge sort work and must be described for full marks.