Cambridge 9618 · International A Level Computer Science · ~16 min read
Notes
Video
Slides
Quiz
Worksheet
Bubble Sort
Bubble sort repeatedly compares adjacent pairs and swaps them if they are in the wrong order. After each pass, the largest unsorted element "bubbles up" to its correct position at the end.
Bubble Sort — Step by Step on [5, 3, 8, 1, 4]
Sorting [5, 3, 8, 1, 4] into ascending order:
Pass 1
3
5
8
1
4
5↔3 swapped; 5<8 no swap; 8↔1 swapped; 8↔4 swapped → 8 in correct place
Pass 2
3
5
1
4
8
3<5 no swap; 5↔1 swapped; 5↔4 swapped → 5 bubbles up
Pass 3
3
1
4
5
8
Pass 4 — no swaps → done
1
3
4
5
8
Bubble Sort — Cambridge 9618 Pseudocode
DECLARE arr : ARRAY[1:5] OF INTEGER DECLARE i, j, temp : INTEGER DECLARE swapped : BOOLEAN
FOR i ← 1TO4// n-1 passes
swapped ← FALSE FOR j ← 1TO5 - i // last i elements already sorted IF arr[j] > arr[j + 1] THEN
temp ← arr[j]
arr[j] ← arr[j + 1]
arr[j + 1] ← temp
swapped ← TRUE ENDIF NEXT j IF NOT swapped THEN// early exit optimisation RETURN ENDIF NEXT i
Bubble Sort Complexity
Worst case: O(n²) — already reverse sorted; all n(n-1)/2 comparisons made. Best case: O(n) — already sorted; one pass with no swaps (with early exit). Average case: O(n²)
Insertion Sort
Insertion sort builds a sorted list one element at a time. Each element is removed from the unsorted portion and inserted into the correct position in the sorted portion — like sorting playing cards in your hand.
Insertion Sort — Step by Step on [5, 3, 8, 1, 4]
Step 1: key = 3, compare with sorted portion [5]
3
5
8
1
4
3 < 5 → shift 5 right, insert 3 in position 1
Step 2: key = 8, compare with sorted [3, 5]
3
5
8
1
4
8 > 5 → already in correct position
Step 3: key = 1, compare with sorted [3, 5, 8]
1
3
5
8
4
1 < 8, < 5, < 3 → shift all right, insert at start
Step 4: key = 4 → Final sorted array
1
3
4
5
8
Insertion Sort — Cambridge 9618 Pseudocode
DECLARE arr : ARRAY[1:5] OF INTEGER DECLARE i, j, key : INTEGER
FOR i ← 2TO5
key ← arr[i] // element to be placed
j ← i - 1// start of sorted portion comparison WHILE j >= 1AND arr[j] > key DO
arr[j + 1] ← arr[j] // shift element right
j ← j - 1 ENDWHILE
arr[j + 1] ← key // insert key in correct position NEXT i
Insertion Sort Complexity
Worst case: O(n²) — reverse sorted; every element must shift past all sorted elements. Best case: O(n) — already sorted; one comparison per element, no shifts. Average case: O(n²)
Merge Sort
Merge sort uses a divide and conquer strategy. The array is repeatedly split in half until each subarray has one element (which is trivially sorted), then the subarrays are merged back in sorted order.
Merge Sort — How it Works
// Merge sort uses recursion PROCEDURE MergeSort(arr, low, high) IF low < high THEN
mid ← (low + high) DIV2
MergeSort(arr, low, mid) // sort left half
MergeSort(arr, mid + 1, high) // sort right half
Merge(arr, low, mid, high) // merge sorted halves ENDIF ENDPROCEDURE
On array [5, 3, 8, 1]:
Split: [5,3] | [8,1]
Split again: [5] | [3] | [8] | [1]
Merge [5] and [3] → [3,5]
Merge [8] and [1] → [1,8]
Merge [3,5] and [1,8] → [1,3,5,8]
Merge Sort Complexity
All cases: O(n log₂ n) — always splits and merges the same way regardless of initial order. Uses extra memory for temporary arrays.
Comparison of Sorting Algorithms
Algorithm
Best case
Average case
Worst case
Memory
Bubble Sort
O(n)*
O(n²)
O(n²)
O(1)
Insertion Sort
O(n)
O(n²)
O(n²)
O(1)
Merge Sort
O(n log n)
O(n log n)
O(n log n)
O(n)
*Bubble sort O(n) best case requires the early exit (swapped flag) optimisation.
Exam tip — tracing bubble sort: Cambridge often asks you to show the array after each pass. Key rules: (1) compare adjacent pairs left to right, (2) swap if left > right, (3) after each pass the largest unsorted element is in its final position. Always show the full array state after each pass, not just swaps.
Swap in Cambridge 9618: Always use a temporary variable: temp ← arr[j]; arr[j] ← arr[j+1]; arr[j+1] ← temp. Never write arr[j] ← arr[j+1]; arr[j+1] ← arr[j] — this overwrites arr[j] before it can be saved.
⚠️ Common Mistakes
Bubble sort inner loop should go from 1 to (n - i), not 1 to n — avoid comparing already-sorted end elements
Swapping without a temp variable — always use a 3-line swap with DECLARE temp
Claiming bubble sort is always O(n) — it's only O(n) with early exit on a nearly-sorted array
Insertion sort: forgetting to restore the key after the WHILE loop — arr[j+1] ← key is essential
Stating merge sort has O(n²) complexity — merge sort is always O(n log n)
Forgetting that merge sort needs O(n) extra memory — it creates additional arrays during the merge step
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 2.4.2 Sorting Algorithms
8 questions · Cambridge 9618 standard
Q1Trace bubble sort on the array [6, 2, 9, 4, 1]. Show the state of the array after each complete pass.[5]
✅ Mark scheme
Pass 1: [2,6,4,1,9] [1]; Pass 2: [2,4,1,6,9] [1]; Pass 3: [2,1,4,6,9] [1]; Pass 4: [1,2,4,6,9] [1]; 4 passes needed [1]. Award marks for correctly showing swaps within each pass.
Q2Write the pseudocode for a 3-line swap of arr[j] and arr[j+1] using a temporary variable.[3]
Q3Explain the purpose of the 'swapped' flag in the optimised bubble sort algorithm.[2]
✅ Mark scheme
If no swaps are made during a pass, the array is already sorted [1]; so the swapped flag allows early exit from the outer loop, improving best-case performance to O(n) [1].
Q4Perform one pass of insertion sort on [7, 2, 5, 1, 8]. Show each step of placing the key element '2'.[3]
✅ Mark scheme
key ← 2 (element at position 2) [1]; compare 2 with 7: 2 < 7, shift 7 right to position 2 [1]; no more elements to compare (j=0), insert key at position 1 → [2,7,5,1,8] [1].
Q5Compare bubble sort, insertion sort and merge sort in terms of worst-case time complexity and memory usage.[4]
✅ Mark scheme
Bubble sort: O(n²) worst case, O(1) memory [1]; Insertion sort: O(n²) worst case, O(1) memory [1]; Merge sort: O(n log n) worst case — consistent for all inputs [1]; Merge sort uses O(n) extra memory for temporary arrays; bubble/insertion sort sort in-place [1].
Q6A programmer has a nearly-sorted array of 10,000 integers and needs to sort it quickly. Which algorithm would you recommend and why?[3]
✅ Mark scheme
Insertion sort [1]; for a nearly-sorted array, insertion sort approaches O(n) because each element needs very few comparisons/shifts [1]; bubble sort with early exit also performs well on nearly-sorted data [1]. Merge sort would be O(n log n) regardless, which is slower than O(n) for nearly-sorted data. (Award 3 max.)
Q7Write a FUNCTION called MaxOfThree that takes three INTEGER parameters and returns the largest value. Write a PROCEDURE called PrintGrade that takes an INTEGER mark and outputs "Pass" if ≥ 50, "Merit" if ≥ 70, otherwise "Fail". Explain why MaxOfThree is a FUNCTION and PrintGrade is a PROCEDURE.[6]
✅ Mark scheme
FUNCTION MaxOfThree(a,b,c : INTEGER) RETURNS INTEGER — 1 mark; IF a > b AND a > c THEN RETURN a ELSIF b > c THEN RETURN b ELSE RETURN c — 1 mark; PROCEDURE PrintGrade(mark : INTEGER) — 1 mark; IF mark ≥ 70 THEN OUTPUT "Merit" ELSIF mark ≥ 50 THEN OUTPUT "Pass" ELSE OUTPUT "Fail" — 1 mark; FUNCTION returns a value used in an expression — 1 mark; PROCEDURE performs actions without returning a value — 1 mark.
Q8Explain what is meant by passing a parameter by value versus by reference. Give a pseudocode example showing both, and explain which is appropriate for a FUNCTION that calculates tax on a salary without changing the salary.[5]
✅ Mark scheme
By value: a copy of the argument is passed; changes inside the procedure do not affect original — 1 mark; by reference: the address is passed; changes inside affect the original variable — 1 mark; BYREF shown with keyword BYREF or &: PROCEDURE Swap(BYREF a,b : INTEGER) — 1 mark; tax calculation should use BYVAL (default) since salary must not be modified — 1 mark; FUNCTION CalcTax(salary : REAL) RETURNS REAL — 1 mark.
Topic Quiz
Question 1 of 10
You scored
out of 10
Card 1 of 6
Click to reveal definition
🎉
All cards reviewed!
Term
Definition
🎯
Mini Test — 2.4.2 Sorting Algorithms
10 questions · 10 marks · 10 minutes
⏱ 10:00
Section A — Multiple Choice [5 marks]
Q1What is the worst-case time complexity of bubble sort?
Q2Which sorting algorithm uses divide and conquer and has O(n log n) complexity in all cases?
Q3During bubble sort, what happens after each complete pass?
Q4In insertion sort, which element is taken during each step?
Q5Why does merge sort use more memory than bubble sort?
Section B — Short Answer [5 marks]
Q6Show the state of [4, 1, 7, 3] after Pass 1 of bubble sort.
Mark schemeCompare 4,1: 4>1 swap → [1,4,7,3] [1]; Compare 4,7: 4<7 no swap; Compare 7,3: 7>3 swap → [1,4,3,7] [1]. After pass 1: [1,4,3,7].
Q7State the purpose of using a temporary variable in a swap. What would go wrong without it?
Mark schemeThe temporary variable preserves the value of arr[j] before it is overwritten [1]; without it, arr[j] ← arr[j+1] would overwrite arr[j], and then arr[j+1] ← arr[j] would just copy arr[j+1] back to itself — the original value of arr[j] would be lost [1].
Q8What is the best-case complexity of insertion sort and in what situation does it occur?
Mark schemeO(n) [1]; occurs when the array is already sorted — each new key element is greater than the last element of the sorted portion, so no shifts are needed, just one comparison per element [1].
Q9Describe, in steps, how merge sort divides and recombines [8, 2, 5, 1].
Mark schemeSplit [8,2,5,1] into [8,2] and [5,1] [1]; split [8,2]→[8],[2] and [5,1]→[5],[1] [1]; merge [8],[2]→[2,8]; merge [5],[1]→[1,5] [1]; merge [2,8] and [1,5]→[1,2,5,8] [1].
Q10State one scenario where bubble sort would be more suitable than merge sort.
Mark schemeAny one of: When memory is very limited (bubble sort is in-place O(1) memory; merge sort uses O(n) extra memory) [1]; when the dataset is very small [1]; when the data is nearly sorted (with early exit, bubble sort approaches O(n)) [1].