- Divide: split the list into two halves. Keep splitting each half until every list holds one item. A list of one item is already sorted, so splitting stops.
- Merge: combine two sorted lists into one sorted list. Compare the front items of both lists, take the smaller one, and repeat until both lists are empty. Keep merging until one list is left.
Merge sort uses divide and conquer, which means breaking a big problem into smaller ones that are easier to solve.
This study notes covers Deep Dive: The Two Stages within Merge Sort for GCSE Computer Science. Revise Merge Sort in 3.1 Fundamentals of Algorithms for GCSE Computer Science with 16 exam-style questions and 10 flashcards. This topic appears less often, but it can still be a useful differentiator on mixed-topic papers. It is section 3 of 8 in this topic. Use this study notes to connect the idea to the wider topic before moving on to questions and flashcards.
Practice questions for Merge Sort
Which design strategy does merge sort use?
Describe how merge sort works. You should include what happens in both the divide and merge phases.
Quick recall flashcards
What technique does merge sort use?
Divide and conquer - splits list in half repeatedly then merges sorted halves
Is merge sort a recursive algorithm?
Yes - it calls itself on smaller sub-lists