AQA 7517 · Paper 1 · 4.3.5

Sorting
Algorithms

Bubble · Merge · Quick · Insertion · Section 4.3 Algorithms

WHAT YOU'LL LEARN

4 sorting algorithms · Pseudocode & traces · O notation · When to use each

AQA SPEC LINK

4.3.5 — Sorting algorithms

Bubble Sort

Repeatedly compares adjacent pairs and swaps if out of order. Largest value "bubbles" to the end each pass. O(n²) worst/average.

FOR pass ← 1 TO LEN(arr) - 1
  swapped ← FALSE
  FOR i ← 0 TO LEN(arr) - pass - 1
    IF arr[i] > arr[i+1] THEN
      temp ← arr[i]; arr[i] ← arr[i+1]; arr[i+1] ← temp
      swapped ← TRUE
    ENDIF
  ENDFOR
  IF NOT swapped THEN RETURN  # optimisation
ENDFOR

Bubble Sort Trace

Bubble Sort — Pass 1 on [5, 3, 8, 1, 4]

      [5, 3, 8, 1, 4] → swap → [3, 5, 8, 1, 4]

      [3, 5, 8, 1, 4] → no swap

      [3, 5, 8, 1, 4] → swap → [3, 5, 1, 8, 4]

      [3, 5, 1, 8, 4] → swap → [3, 5, 1, 4, 8]

      After pass 1: [3, 5, 1, 4, 8] ← 8 in final position

Merge Sort

Merge Sort — Divide & Conquer

Recursively splits list into halves until single elements, then merges back in sorted order. O(n log n) guaranteed. Stable sort.

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

    [5, 3] → split → [5] [3] → merge → [3, 5]

    [8, 1] → split → [8] [1] → merge → [1, 8]

    [3, 5] + [1, 8] → merge → [1, 3, 5, 8]

Quick Sort

Quick Sort — Pivot-based

Choose a pivot. Partition: items less than pivot left, greater right. Recursively sort each partition. O(n log n) average, O(n²) worst (bad pivot).

    [5, 3, 8, 1, 4] — pivot = 5

    Less than 5: [3, 1, 4]  |  5  |  Greater: [8]

    Sort [3, 1, 4] → pivot=3: [1] 3 [4]

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

Insertion Sort

Builds sorted portion one item at a time by inserting each element into its correct position. Good for nearly sorted data. O(n²) worst, O(n) best.

    [5, 3, 8, 1] — start with [5]

    Insert 3: [3, 5]

    Insert 8: [3, 5, 8]

    Insert 1: [1, 3, 5, 8]

Complexity Comparison

Sorting Algorithm Complexity

Algorithm	Best	Average	Worst	Space
Bubble	O(n)	O(n²)	O(n²)	O(1)
Insertion	O(n)	O(n²)	O(n²)	O(1)
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)
Quick	O(n log n)	O(n log n)	O(n²)	O(log n)

When to Use

Choosing the Right Sort

Bubble Sort — simple to implement; only useful for small n or teaching

Insertion Sort — good for nearly sorted or very small lists; O(n) best case

Merge Sort — guaranteed O(n log n); preferred when worst case matters; uses extra O(n) space

Quick Sort — fastest in practice; O(n log n) average; poor pivot choice → O(n²)

AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style

An array contains: [7, 2, 9, 3, 6]
(a) Show the state of the array after each pass of a bubble sort. [4]
(b) State the worst-case time complexity of merge sort. [1]
(c) Give ONE advantage of merge sort over bubble sort for large datasets. [1]

[6 marks]

4 marks

(a) Pass 1: [2,7,3,6,9] | Pass 2: [2,3,6,7,9] | Pass 3: [2,3,6,7,9] (sorted — swap flag not set)

1 mark

(b) O(n log n)

1 mark

(c) Merge sort is O(n log n) compared to bubble sort's O(n²) — significantly faster for large n

Summary

Key Points to Remember

Bubble Sort — O(n²); compare adjacent pairs; swap optimisation with flag

Insertion Sort — O(n²) worst; O(n) best; good for nearly sorted

Merge Sort — O(n log n) guaranteed; divide & conquer; needs extra O(n) space

Quick Sort — O(n log n) average; O(n²) worst (degenerate pivot)

AQA uses temp variable swap syntax in pseudocode

🎉 Lesson complete — move to the quiz!