Key Terms
- Merge sort: Splits the list into single items, then merges them back in order
- Divide and conquer: Splitting a problem into smaller parts and solving each part
- Merge step: Combines two sorted lists into one sorted list
Must-Know Facts
- Merge sort has two stages: divide, then merge
- Splitting stops when every list holds one item
- The merge step compares the front items of two sorted lists and takes the smaller
- An 8 item list is divided three times to reach single items
- Merge sort is much faster than bubble sort on large lists
- Its main drawback is the extra memory needed for the merged lists
Key Concepts
- Split, split, split to single items, then merge in order
- Each merge builds a bigger sorted list from two smaller sorted lists
- Bubble sort and insertion sort work in place, but merge sort does not
- For a large list, merge sort is the better choice despite the memory cost
- In exams: show every divide step and every merge step
Common Mistakes
- Swapping neighbours: That is bubble sort. Merge sort splits and merges
- Taking the larger front item first: For ascending order the merge step takes the smaller item
- Saying merge sort needs no extra memory: It needs space to hold the lists it merges
- Forgetting to show the divide stage: Marks are given for both the divide and the merge steps
- Saying merge sort is always best: It is faster on large lists, but for a short list a simple sort is fine and uses less memory
This topic summary covers Knowledge Organiser: Merge Sort 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 8 of 8 in this topic. Use this topic summary 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
Is merge sort a recursive algorithm?
Yes - it calls itself on smaller sub-lists
What technique does merge sort use?
Divide and conquer - splits list in half repeatedly then merges sorted halves