Cambridge 9618 · International A Level Computer Science · ~18 min read
Notes
Video
Slides
Quiz
Worksheet
Why Sorting Matters
Sorting is a fundamental operation in computing. Sorted data enables efficient searching (binary search requires sorted data), presentation of ordered results, and efficient merging of datasets. Cambridge 9618 Paper 4 requires knowledge of four sorting algorithms: bubble sort, insertion sort, merge sort, and quick sort.
Bubble Sort
🫧 Bubble Sort
O(n²) averageO(n) best caseStable
Repeatedly compare ADJACENT pairs and swap them if in the wrong order. After each pass, the LARGEST unsorted element "bubbles" to the correct position at the end. Continue until no swaps occur in a full pass (early termination).
Key facts: Simple to implement. Efficient only for nearly-sorted data (O(n) best case with early termination flag). Stable sort (equal elements preserve original order). In-place (O(1) extra space).
// Bubble sort with early termination PROCEDUREBubbleSort(Arr, n) FORi ← 1TOn-1 swapped ← FALSE FORj ← 1TOn-i IFArr[j] > Arr[j+1] THEN Swap(Arr[j], Arr[j+1]) swapped ← TRUE ENDIF NEXTj IF NOTswappedTHEN EXIT FOR// already sorted NEXTi ENDPROCEDURE
Insertion Sort
📥 Insertion Sort
O(n²) averageO(n) best caseStable
Builds a sorted portion one element at a time. For each new element, insert it into the correct position in the already-sorted portion by shifting elements right. Like sorting playing cards in your hand.
Key facts: Very efficient for small or nearly-sorted datasets. O(n) best case (already sorted — no shifts needed). Stable sort. In-place. Better than bubble sort in practice for most cases.
A divide-and-conquer algorithm. Recursively DIVIDE the array in half until each sub-array has one element (already sorted). Then MERGE pairs of sorted sub-arrays back together.
Key facts: Guaranteed O(n log n) — not affected by input order. Stable. But requires O(n) extra memory for the temporary merge buffer. Best for large datasets where predictable performance is needed.
Divide-and-conquer. Choose a PIVOT element. Partition the array into elements < pivot (left) and elements > pivot (right). Recursively sort each partition.
Key facts: Average O(n log n) — fastest in practice. Worst case O(n²) when pivot is always the smallest or largest (sorted/reverse-sorted input). In-place (O(log n) stack space for recursion). Not stable. Pivot choice matters — middle or random pivot avoids worst case.
Bubble/Insertion sort: Small datasets (<20 elements) or nearly-sorted data; when simplicity matters
Merge sort: Large datasets; when guaranteed O(n log n) is needed; when stability matters; when sorting linked lists
Quick sort: General purpose; large datasets in practice (best constant factor despite same O notation as merge)
Cambridge 9618 exam tip: Know how to TRACE each algorithm on a given small array — examiners frequently give 5-6 element arrays and ask for the state after each pass or step. For bubble sort: show comparisons and swaps pass-by-pass. For insertion sort: show the sorted portion growing and where each key is inserted. For merge sort: show the divide steps then the merge steps. For quick sort: show the pivot and partition. Know time complexities for best/average/worst case. "Stable" means equal elements maintain their original relative order — important when sorting objects with multiple fields.
⚠️ Common Mistakes
Forgetting early termination in bubble sort — without the swap flag (swapped = FALSE at start of each pass), bubble sort is always O(n²). WITH the flag, it exits early if the array becomes sorted mid-way, giving O(n) best case.
Insertion sort starting index — insertion sort starts from index 2 (the SECOND element), treating the first element as an already-sorted list of one. Starting at index 1 misses the first element.
Quick sort worst case — O(n²) occurs when the pivot is always the minimum or maximum element (e.g. sorted array with first/last pivot choice). Always mention this when describing quick sort.
Merge sort space — merge sort requires O(n) EXTRA memory for the temporary arrays used during merging. It is NOT in-place. Quick sort is in-place (O(log n) stack space for recursion only).
Stability — only bubble sort, insertion sort, and merge sort are stable. Quick sort is NOT stable — equal elements may be reordered. This matters when sorting records with multiple keys.
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 4.4.1 Sorting Algorithms
8 questions · Cambridge 9618 standard
Q1Trace bubble sort on the array [5, 1, 4, 2, 8]. Show the state of the array after each complete pass. Use the swap flag for early termination where possible.[5]
✅ Mark scheme
Pass 1: [5,1]→swap [1,5]; [5,4]→swap [1,4,5]; [5,2]→swap [1,4,2,5]; [5,8]→no swap. After pass 1: [1, 4, 2, 5, 8] swapped=TRUE [1]; Pass 2: [1,4]→no swap; [4,2]→swap [1,2,4]; [4,5]→no swap. After pass 2: [1, 2, 4, 5, 8] swapped=TRUE [1]; Pass 3: [1,2]→no swap; [2,4]→no swap; [4,5]→no swap. After pass 3: [1, 2, 4, 5, 8] swapped=FALSE → early termination [1]; Award 1 mark per correct pass state [3 marks], 1 mark for showing early termination flag [1], 1 mark for identifying no swap on pass 3 causes exit [1]. Total 5 marks.
Q2Trace insertion sort on [29, 10, 14, 37, 13]. Show the sorted portion after each step (each time a new element is inserted).[4]
Q3Explain the divide-and-conquer approach used by merge sort. State the two main phases and what happens in each.[4]
✅ Mark scheme
Divide phase: the array is repeatedly split in half — the left half and right half are each split again, recursively, until each sub-array contains only one element [1]; a single-element array is trivially sorted (base case) [1]; Merge phase: pairs of sorted sub-arrays are merged back together by comparing their front elements — the smaller goes into the merged array first; this repeats until one sub-array is exhausted, then the remainder is appended [1]; the merge phase produces larger and larger sorted arrays until the entire array is sorted [1]. The key insight is that merging two already-sorted arrays takes O(n) time, and the log n levels of division give O(n log n) total.
Q4Quick sort uses a pivot. Trace one partitioning step on [8, 3, 6, 1, 9, 4] using the last element (4) as pivot. Show the left partition, pivot, and right partition.[3]
✅ Mark scheme
Pivot = 4 (last element) [1]; Left partition (elements < 4): [3, 1] [1]; Right partition (elements > 4): [8, 6, 9] [1]; After one partition: [3, 1] | 4 | [8, 6, 9] — 4 is now in its FINAL sorted position. Recursively sort [3,1] → [1,3] and [8,6,9] → [6,8,9]. Final: [1,3,4,6,8,9]. Award all 3 marks for correct identification of pivot, left and right partitions, noting pivot is in final position.
Q5State the worst-case time complexity of quick sort and describe the input scenario that causes it. Explain how this can be avoided.[3]
✅ Mark scheme
Worst case O(n²) [1]; occurs when the pivot chosen is always the minimum or maximum element of the current partition — this creates highly unbalanced partitions (one side has n-1 elements, the other has 0); this happens when the array is already sorted (or reverse-sorted) and the pivot is always the first or last element [1]; avoidance: choose the pivot more carefully — options: (a) median-of-three: compare first, middle, and last elements and use the median as pivot; (b) random pivot selection: randomly choose a pivot position — makes worst case extremely unlikely; (c) use the middle element as pivot rather than first/last [1].
Q6Explain what is meant by a "stable" sorting algorithm. State which of the four sorting algorithms (bubble, insertion, merge, quick) are stable and which are not.[3]
✅ Mark scheme
A stable sorting algorithm preserves the ORIGINAL RELATIVE ORDER of elements that are equal (have the same sort key) [1]; example: if sorting [(Alice, 87), (Bob, 92), (Carol, 87)] by score, a stable sort would output Alice before Carol since Alice appears first in the original; an unstable sort might output Carol before Alice despite equal scores [1]; Stable: bubble sort, insertion sort, merge sort; NOT stable: quick sort [1]. Quick sort's partition step can move equal elements past each other in non-predictable ways, losing original ordering.
Q7Trace the bubble sort algorithm on the array [5, 3, 8, 1, 9] for ONE complete pass. Show the array state after each swap. State how many comparisons and how many swaps are made in this first pass.[5]
Q8Compare merge sort and insertion sort in terms of: (a) time complexity for best and worst case, (b) suitability for nearly-sorted data, (c) memory usage. Recommend which to use when sorting 100,000 random integers, justifying your answer.[6]
✅ Mark scheme
(a) Merge sort: O(n log n) best and worst; Insertion sort: O(n) best (nearly sorted), O(n²) worst [2]; (b) Insertion sort is highly efficient for nearly-sorted data; merge sort always O(n log n) regardless [1]; (c) Merge sort requires O(n) extra memory for merging; insertion sort is in-place O(1) extra space [1]; Recommendation: merge sort for 100,000 random integers [1]; justification: guaranteed O(n log n) performance avoids O(n²) worst case of insertion sort on large random data [1].
Topic Quiz
Question 1 of 10
You scored
out of 10
Card 1 of 8
Click to reveal definition
🎉
All cards reviewed!
Term
Definition
🎯
Mini Test — 4.4.1 Sorting
10 questions · 10 marks · 10 minutes
⏱ 10:00
Section A — Multiple Choice [5 marks]
Q1What is the average-case time complexity of merge sort?
Q2Which sorting algorithm is NOT stable?
Q3Bubble sort achieves O(n) best case when:
Q4Which algorithm requires O(n) extra memory for merging?
Q5When does quick sort degrade to O(n²) worst case?
Section B — Short Answer [5 marks]
Q6Write the state of array [6, 2, 8, 4] after each complete pass of bubble sort.
Mark schemePass 1: [6,2]→swap; [6,8]→no swap; [8,4]→swap → [2, 6, 4, 8] swapped=TRUE [1]; Pass 2: [2,6]→no swap; [6,4]→swap; → [2, 4, 6, 8] swapped=TRUE [1]; Pass 3: [2,4]→no; [4,6]→no → no swaps → [2, 4, 6, 8] swapped=FALSE → STOP [1]. Three marks: 1 per correct pass state including swap/no-swap notation where shown.
Q7Explain why insertion sort is particularly efficient for nearly-sorted data. What is its time complexity in this case?
Mark schemeIn insertion sort, each element is compared with those in the sorted portion and shifted until its correct position is found; for nearly-sorted data, each new element only needs to be shifted a small number of positions (often zero or one) — very few comparisons and shifts are needed [1]; in the best case (already sorted input), no element needs to be shifted at all — the WHILE loop condition fails immediately for every element, giving O(n) time (one comparison per element just to confirm correct position) [1]; time complexity for nearly-sorted: O(n) best case to O(n²) average — approaches O(n) as data approaches sorted order [1].
Q8Explain the role of the pivot in quick sort. Why does the choice of pivot matter?
Mark schemeThe pivot is an element chosen from the array to partition it: all elements LESS than the pivot go to one side, all elements GREATER go to the other side; after partitioning, the pivot is in its FINAL correct sorted position [1]; pivot choice matters because it determines partition balance: an ideal pivot (the true median) splits the array into two roughly equal halves — giving O(n log n) time [1]; a poor pivot (e.g. always the minimum or maximum, as happens with sorted input using first/last pivot) creates heavily unbalanced partitions of sizes 0 and n-1 — leading to O(n²) worst case [1].
Q9State one advantage of merge sort over quick sort and one advantage of quick sort over merge sort.
Mark schemeMerge sort advantage: guaranteed O(n log n) in ALL cases — no worst case deterioration; quick sort can degrade to O(n²) on sorted input with poor pivot choice; merge sort is always predictable [1]; merge sort is also STABLE — equal elements preserve their original order; quick sort is not stable [accept as alternative]; Quick sort advantage: in-place — uses only O(log n) extra stack space (for recursion); merge sort requires O(n) extra memory for the temporary merge buffer; quick sort is more space-efficient [1]; in practice quick sort has smaller constant factors in its O notation, making it faster in real-world use despite same O(n log n) average complexity [accept as alternative].
Q10Show the complete divide phase of merge sort on the array [5, 2, 8, 3, 9, 1]. Show each split step.
Mark schemeLevel 0: [5, 2, 8, 3, 9, 1] [1]; Level 1 (split in half): [5, 2, 8] | [3, 9, 1] [1]; Level 2 (split each half): [5, 2] | [8] | [3, 9] | [1] [1]; Level 3 (split again): [5] | [2] | [8] | [3] | [9] | [1] — all single elements, base case reached [1]; Note: with 6 elements split unevenly, the exact split points may vary slightly (3+3 or 4+2 depending on implementation) — award marks for any consistent halving approach that reaches all single elements. Then merge phase begins.