Skip to main content
EnglandComputer ScienceSyllabus dot point

How do computers put a list of values into order?

Understand and explain how the bubble sort and merge sort algorithms work, trace each one, and compare them in terms of method and efficiency.

A focused answer to AQA GCSE Computer Science 3.1.4, covering how bubble sort and merge sort work, how to trace each one, and how they compare in method and efficiency.

Generated by Claude Opus 4.88 min answer

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section
  1. What this dot point is asking
  2. Bubble sort
  3. Merge sort
  4. Comparing the two
  5. Tracing a sort in the exam
  6. Why efficiency matters
  7. Try this

What this dot point is asking

AQA wants you to explain how bubble sort and merge sort work, trace each one on a list of values, and compare them in terms of how they work and how efficient they are.

Bubble sort

It is simple to write and sorts in place (no extra lists needed) but is slow, because for a list of nn items it may need close to n2n^2 comparisons in the worst case.

Merge sort

The merge step compares the front items of two sorted sub-lists and takes the smaller each time, which is why merging is efficient. Splitting and merging means merge sort needs at most about nlog⁡2nn \log_2 n operations, far fewer than bubble sort on large lists.

Comparing the two

Tracing a sort in the exam

Sort questions often ask you to show the list after each pass or each merge, so set your working out clearly. For a bubble sort, write the list at the start of each pass and after every swap, and note that after pass kk the largest kk values are in place at the end, so each pass can stop one position earlier. For a merge sort, draw the splitting as a tree down to single items, then show each merge of two sorted sub-lists, taking the smaller front item each time. Laying the trace out step by step earns method marks even if a single comparison slips, and it makes it obvious when the list is finally sorted.

Why efficiency matters

The reason the specification pairs a slow simple sort with a fast complex one is to make the efficiency point concrete. Bubble sort's roughly n2n^2 comparisons grow far faster than merge sort's roughly nlog⁡2nn \log_2 n as the list lengthens, so the gap is tiny for a handful of items but enormous for millions. The trade-off is that merge sort needs extra memory for the temporary lists it builds while merging, whereas bubble sort sorts in place. So the right choice depends on the data: bubble sort for small or nearly sorted lists, merge sort when the list is large and speed matters more than memory.

Try this

Q1. Describe the main idea of a bubble sort. [2 marks]

  • Cue. Repeatedly compare adjacent pairs and swap if in the wrong order, passing through the list until no swaps are made.

Q2. State the technique that merge sort is based on. [1 mark]

  • Cue. Divide and conquer: split the list down to single items, then merge them back in order.

Exam-style practice questions

Practice questions written in the style of AQA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

AQA 20194 marksTrace one complete pass of a bubble sort on the list [6, 2, 9, 4]. State the list after each swap and the list at the end of the pass.
Show worked answer →

Compare adjacent pairs left to right, swapping when the left value is larger.

Compare 6 and 2: swap to give [2, 6, 9, 4]. Compare 6 and 9: no swap, [2, 6, 9, 4]. Compare 9 and 4: swap to give [2, 6, 4, 9].

After one full pass the list is [2, 6, 4, 9], and the largest value 9 has bubbled to the end (its correct place).

Markers reward correct adjacent comparisons, showing each swap, and the end-of-pass list with the largest value settled at the end.

AQA 20225 marksCompare bubble sort and merge sort in terms of how they work and their efficiency on a large list. Recommend which is more suitable for sorting one million records and justify your answer.
Show worked answer →

Bubble sort repeatedly compares and swaps adjacent items, passing through the list until no swaps occur; it sorts in place with little extra memory but is slow, needing up to about n2n^2 comparisons. Merge sort uses divide and conquer: it splits the list down to single items then merges them back in order, needing about nlog⁡2nn \log_2 n operations, but uses more memory for the temporary lists.

For one million records, merge sort is far more suitable: n2n^2 for bubble sort is around 101210^{12} operations, whereas nlog⁡2nn \log_2 n for merge sort is around 2×1072 \times 10^7, so merge sort finishes vastly faster. The extra memory is an acceptable cost for that speed.

Markers reward the method contrast, the efficiency figures (n2n^2 versus nlog⁡2nn \log_2 n), and a justified recommendation tied to the large data size.

Related dot points

Sources & how we know this