Test yourself on Merge Sort with exam style questions, marked instantly.
Flashcards that come back just before you would forget them.
A revision plan that remembers what you know and shows what to do next.
See which topics you have nailed and which need another look.
Quiz yourself on Merge SortGet your flashcardsBuild my revision planTrack my progressSplit It, Sort It, Join It
Merge sort is like sorting a huge pile of exam papers with friends. You split the pile in half, then split again, until everyone holds a single paper (one paper is already sorted). Then you pair up and merge the small sorted piles into bigger sorted piles, until one sorted pile is left.
Bubble sort compares neighbouring items and swaps them if they are in the wrong order, then repeats the pass. Merge sort divides the list down to single items, then merges the sorted parts back together. Insertion sort inserts each item into the sorted part. On long lists bubble sort and insertion sort make many comparisons, and merge sort makes fewer. Bubble sort and merge sort are named by OCR, AQA and Edexcel. Insertion sort is named by OCR only.
Merge Sort or Bubble Sort?
| Feature | Merge Sort | Bubble Sort |
|---|---|---|
| Method | Divide the list, then merge sorted lists | Compare neighbours and swap |
| Speed on large lists | Much faster | Slow |
| Extra memory | Needs extra space for the lists it merges | None, it sorts in place |
| Ease of coding | Harder to program | Simple |
Deep Dive: The Two Stages
- 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.
Deep Dive: Merge Sort Trace
Sort [6, 2, 8, 4]:
Divide:
- [6, 2, 8, 4] splits into [6, 2] and [8, 4]
- [6, 2] splits into [6] and [2]. [8, 4] splits into [8] and [4].
Merge:
- Merge [6] and [2]: compare 6 and 2, take 2, then 6. Result [2, 6].
- Merge [8] and [4]: compare 8 and 4, take 4, then 8. Result [4, 8].
- Merge [2, 6] and [4, 8]: compare 2 and 4, take 2. Compare 6 and 4, take 4. Compare 6 and 8, take 6. Only 8 is left, take 8.
- Result: [2, 4, 6, 8]
Deep Dive: Merging Two Lists
Merge [2, 5] with [1, 4]:
| Compare | Take | Merged list so far |
|---|---|---|
| 2 and 1 | 1 | [1] |
| 2 and 4 | 2 | [1, 2] |
| 5 and 4 | 4 | [1, 2, 4] |
| Only 5 left | 5 | [1, 2, 4, 5] |
For an 8 item list, the splits give 2 lists of 4, then 4 lists of 2, then 8 lists of 1. That is three divisions.
Memory Trick
Split, split, split, then merge, merge, merge. Divide until every list has one item, then build the sorted list back up.
Merge always takes the smaller front item when sorting into ascending order.
Exam Tips
- Show both stages: draw the divide steps and then the merge steps.
- Merge advantage: much faster than bubble sort on large lists.
- Merge disadvantage: needs extra memory and is harder to program.
- Common mistake: sorting the halves while splitting. Nothing is sorted until the merge stage.
Make this stick
Signing in gives access to all PrepWise features.