Bubble sort and merge sort

Two sorting algorithms are on the AQA GCSE specification — bubble sort (simple, slow) and merge sort (more complex, much faster on large lists).

Bubble sort — the idea

Repeatedly walk through the list comparing adjacent pairs. Swap any pair that's in the wrong order. After one full pass, the largest item has "bubbled" to the end. Repeat with one fewer item until no swaps occur in a full pass.

SET swapped TO true
WHILE swapped = true
  SET swapped TO false
  FOR i FROM 0 TO LEN(list) - 2
    IF list[i] > list[i+1] THEN
      Swap list[i] and list[i+1]
      SET swapped TO true
    ENDIF
  ENDFOR
ENDWHILE

• Worst case: $\tfrac{n(n-1)}{2}$ comparisons.
• Best case (already sorted): $n − 1$ comparisons (one pass with no swaps).
• Memory: tiny — sorts in place.

Bubble sort trace

Sort [5, 3, 8, 1] ascending:

Pass	Compare	Action	List
1	5,3	swap	[3, 5, 8, 1]
1	5,8	no swap	[3, 5, 8, 1]
1	8,1	swap	[3, 5, 1, 8]
2	3,5	no swap	[3, 5, 1, 8]
2	5,1	swap	[3, 1, 5, 8]
2	5,8	no swap	[3, 1, 5, 8]
3	3,1	swap	[1, 3, 5, 8]
3	3,5,8	no swaps	[1, 3, 5, 8]

Sorted after pass 4 (no swaps).

Merge sort — the idea

A divide-and-conquer algorithm:

1. Divide the list into halves until each sub-list has 1 item.
2. Merge pairs of sub-lists in sorted order: compare the fronts, take the smaller one, repeat until both are empty.

FUNCTION mergeSort(list)
  IF LEN(list) <= 1 THEN
    RETURN list
  ENDIF
  SET mid TO LEN(list) DIV 2
  SET left TO mergeSort(list[0:mid])
  SET right TO mergeSort(list[mid:])
  RETURN merge(left, right)
ENDFUNCTION

• Worst case: $n \log_2 n$ comparisons.
• Memory: needs extra arrays during merging — not in-place.
• Reliable performance — the worst case and average case are the same.

Merge sort trace

Sort [5, 3, 8, 1, 9, 2]:

• Split: [5,3,8] | [1,9,2]
• Split: [5] [3,8] | [1] [9,2]
• Split: [5] [3] [8] | [1] [9] [2]
• Merge: [3,5] [8] | [1] [2,9] (and [8] alone)
• Merge: [3,5,8] | [1,2,9]
• Final merge: [1,2,3,5,8,9]

Comparing the two

Property	Bubble sort	Merge sort
Easy to code	Yes	No (recursion)
In-place?	Yes	No (needs RAM)
Worst case	$n^2$	$n \log_2 n$
Best case	$n$	$n \log_2 n$
Stable?	Yes	Yes
Good for big lists?	No	Yes

For $n = 1000$:

• Bubble: ~500{,}000 comparisons.
• Merge: ~10{,}000 comparisons.

For $n = 1{,}000{,}000$:

• Bubble: 5 × 10¹¹ — minutes/hours.
• Merge: 2 × 10⁷ — seconds.

When to use bubble sort

Almost never in real code, but it's:

• Easy to understand and teach.
• Fast for nearly-sorted small lists (best case is linear).
• Tiny memory footprint.