CAIE 9618 · Paper 4 · Topic 4.4.1

Sorting
Algorithms

Bubble Sort · Insertion Sort · Merge Sort · Quick Sort · Complexity Comparison

CSZone Cambridge International AS & A Level Computer Science 9618

Bubble Sort & Insertion Sort

Simple O(n²) Algorithms

Bubble Sort

Compare adjacent pairs; swap if out of order

Largest element "bubbles" to the end each pass

Repeat n-1 passes; early termination if no swaps

Pass 1: [5,3,8,1] → [3,5,8,1] → [3,5,1,8]
— 8 is now sorted in correct position

Time: O(n²) worst/avg. O(n) best (sorted). Space: O(1)

Insertion Sort

Build sorted portion one element at a time from left

Take next unsorted element; shift sorted elements right until correct position found; insert

Very efficient on nearly-sorted data and small n

Stable sort — preserves original order of equal elements

[5] | 3,8,1 → take 3, shift 5 right → [3,5] | 8,1
→ take 8, no shift → [3,5,8] | 1
→ take 1, shift 5,8 right → [1,3,5,8] ✓

Time: O(n²) worst/avg. O(n) best. Space: O(1)

Merge Sort & Quick Sort

Efficient O(n log n) Algorithms

Merge Sort — Divide & Conquer

Recursively divide list into halves until single elements

Merge pairs of sorted sub-lists by comparing heads

Stable sort; guaranteed O(n log n) regardless of input

Requires O(n) extra space for temporary arrays

[5,3,8,1] → [5,3] [8,1]
→ [5][3] [8][1]
→ [3,5] [1,8]
→ [1,3,5,8] ✓

Quick Sort — Pivot & Partition

Choose a pivot element (often first, last, or median)

Partition: elements smaller than pivot go left, larger go right

Recursively quick sort each partition

O(n log n) average; O(1) space (in-place)

O(n²) worst case — already sorted array with bad pivot choice

Pivot = 5: [3,1] | 5 | [8]
Pivot = 3: [1] | 3 | [] → [1,3,5,8] ✓

Comparison Table

Which Algorithm When?

Algorithm	Best	Average	Worst	Space	Stable?	Best for
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Small/nearly-sorted data
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Small n, streaming data
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	Large n, stability required
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No	General purpose, large n

CAIE EXAM TIP — What Is a Stable Sort?

A stable sort preserves the relative order of equal elements. If two students have the same score, a stable sort keeps them in their original order. Bubble sort and insertion sort are stable; quick sort is not; merge sort is stable.

Exam Practice

Cambridge-style questions

Question 1

The list [7, 2, 9, 4, 1] is to be sorted in ascending order. Show the state of the list after each pass of bubble sort. State how many comparisons are made in the first pass. [4]

1

Pass 1: compare (7,2)→swap, (7,9)→no swap, (9,4)→swap, (9,1)→swap → [2,7,4,1,9]. 9 is now in its final position. 4 comparisons made.

1

Pass 2: [2,7,4,1,9] → compare (2,7)→no, (7,4)→swap, (7,1)→swap → [2,4,1,7,9].

1

Pass 3: [2,4,1,7,9] → (2,4)→no, (4,1)→swap → [2,1,4,7,9].

1

Pass 4: [2,1,4,7,9] → (2,1)→swap → [1,2,4,7,9] ✓. Number of comparisons in first pass: 4 (n-1 for n=5).

Common Mistakes

Don't lose easy marks

1

Saying "merge sort uses O(1) memory" — merge sort requires O(n) extra space for the temporary arrays used during the merge step. Quick sort is the in-place algorithm that uses only O(log n) stack space.

2

Getting bubble sort passes wrong in trace questions — after each full pass, the LARGEST unsorted element is at its correct position (not the smallest). Work carefully from left to right comparing adjacent pairs.

3

Saying "quick sort is always O(n log n)" — quick sort is O(n²) in the worst case when the pivot is always the smallest or largest element (e.g. already sorted data with first-element pivot). This is why random or median-of-three pivot selection improves practical performance.

Topic Summary — 4.4.1

What You Need to Know

BUBBLE & INSERTION SORT

O(n²) average. O(n) best (sorted). O(1) space. Stable. Simple to implement. Good for small/nearly-sorted data. Know how to trace each pass.

MERGE SORT

Always O(n log n). Stable. O(n) extra space. Divide recursively → merge. Good for large n and linked lists. Guaranteed performance.

QUICK SORT

O(n log n) avg, O(n²) worst. O(log n) space (in-place). Not stable. Choose pivot, partition, recurse. Fastest in practice for large n. Unstable worst case.

CSZone

Next Video

4.4.2

Searching & Graph Algorithms

Linear · Binary Search · BFS · DFS · Dijkstra

Head to CSZone.co.uk for the complete worksheet, quiz, and interactive tools