Sorting — Bubble & Merge

Spec & Goals 3 min

AQA Spec 3.1.4 · Sorting algorithms

By the end of this lesson you can:

1. Carry out a bubble sort, performing each comparison, swap and pass in order.
2. Describe how a merge sort splits a list and then merges it back in order.
3. Give a reason a merge sort beats a bubble sort on a large list.

Warm-Up 5 min

Last lesson you searched a list with linear and binary search. Today you sort one.

Quick starter

You hold four cards: [5, 3, 8, 1]. Compare the first two cards only.

• Is 5 bigger than 3? What should you do?

Key Concept — bubble sort & merge sort 14 min

A sorting algorithm puts a list of values into order — usually smallest to largest (ascending).

Bubble sort

Bubble sort works through the list comparing each adjacent pair:

• Compare two items next to each other.
• Swap them if they are in the wrong order.
• Move along to the next pair and repeat to the end of the list — that is one pass.
• Repeat passes until a pass makes no swaps; the list is then sorted.

AQA pseudo-code — bubble sort

REPEAT
  swapped ← FALSE
  FOR i ← 0 TO LEN(list) − 2
    IF list[i] > list[i + 1] THEN
      temp ← list[i]
      list[i] ← list[i + 1]
      list[i + 1] ← temp
      swapped ← TRUE
    ENDIF
  ENDFOR
UNTIL swapped = FALSE

The temp variable holds one value while the two are exchanged. The loop stops once a whole pass finishes with no swap.

Merge sort

Merge sort uses a different idea — split then merge:

• Repeatedly split the list in half until each part holds a single item.
• A list of one item is already sorted.
• Then merge the parts back together, two at a time, always in order.

Worked Example — one bubble pass, then merge 12 min

Problem: sort [5, 3, 8, 1]. First do one full pass of a bubble sort.

A pass compares each adjacent pair, left to right, swapping when the left value is larger:

After pass 1: [3, 5, 1, 8]. The largest value, 8, has "bubbled" to the end. The list is not yet sorted, so another pass is needed.

The same bubble sort in Python

numbers = [5, 3, 8, 1]
swapped = True
while swapped:
    swapped = False
    for i in range(len(numbers) - 1):
        if numbers[i] > numbers[i + 1]:
            numbers[i], numbers[i + 1] = numbers[i + 1], numbers[i]
            swapped = True
print(numbers)

Now the same list sorted by merge sort — split to singles, then merge back in order:

Try It Yourself 12 min

📝 Exam Practice 10 min

Answer the way the examiner expects — the command word and the marks tell you how much to write.

Recap & Key Terms 3 min

A sorting algorithm orders a list. Bubble sort compares adjacent pairs and swaps, repeating passes until none are needed. Merge sort splits the list to single items, then merges them back in order — faster on large lists.

Sorting algorithm

An algorithm that arranges the values in a list into order.

Bubble sort

Repeatedly compares adjacent pairs and swaps them if out of order, until a pass makes no swaps.

Pass

One full sweep through the list, comparing every adjacent pair once.

Swap

Exchanging two values so they are in the correct order.

Merge sort

Splits the list in half repeatedly to single items, then merges the parts back together in order.

Homework 1 min

Task (≤ 15 min): Carry out a full bubble sort on [6, 2, 4, 1], writing the list after each pass until it is sorted.