AQA 7517 4.3.5.2: Merge sort
The free BugBot lesson that teach this point, a robot to try it on, and the past-paper questions that test it.
What it covers
At GCSE (F5.9) you split a list into ones and merged them back together, and saw merge sort beat bubble sort on a big list. At A level you write merge sort recursively, trace it, and show why it is O(n log n) in every case, and what it costs in memory.
- Divide and conquer
- A trace
- In pseudocode
- Why it is O(n log n)
- The cost: memory
Or do it in the simulator, with tasks that mark themselves
Lessons that teach it
- A5.5 Merge sort Algorithms and complexity
Divide and conquer, a recursive merge sort, why it is O(n log n) in every case, and its O(n) memory cost.
Try it on a robot
The task from A5.5 Merge sort, running here. Change the program and press Run.
The specification is AQA's own document; this page says which of our lessons teach point 4.3.5.2 and is not endorsed by the board.