Merge Sort (AQA GCSE Computer Science): Revision Notes
Merge sort
What is merge sort?
Merge sort is a powerful sorting algorithm that uses a divide and conquer approach to organise data. Unlike simpler algorithms like bubble sort, merge sort splits your data into smaller pieces first, then cleverly puts them back together in the correct order.
Think of it like this: if you had to sort a massive pile of playing cards, it would be much easier to split them into smaller piles first, sort those individually, then combine them back together. That's exactly what merge sort does!
How merge sort works
The merge sort algorithm works in two main stages:
Stage 1: Divide
The algorithm starts by splitting your list of numbers in half, over and over again, until each piece contains just one number. Since a single number is automatically "sorted," this gives us our starting point.
Stage 2: Conquer (merge)
Now comes the clever part! The algorithm takes pairs of these tiny lists and merges them together, but keeps them in order as it goes. This process continues until all the numbers are combined back into one fully sorted list.
The key insight is that merge sort breaks down a complex problem (sorting many numbers) into simpler problems (sorting just a few numbers), then builds the solution back up systematically.
Step-by-step example
Worked Example: Sorting with Merge Sort
Let's work through sorting these numbers: 7, 2, 9, 4, 3, 8, 5, 1
Step 1: Divide into individual elements First, we keep splitting the list in half until we have individual numbers:
Step 2: Start merging pairs Now we begin merging pairs of numbers, making sure to put the smaller number first:
- 7 and 2 become 2, 7
- 9 and 4 become 4, 9
- 3 and 8 become 3, 8
- 5 and 1 become 1, 5
Step 3: Merge the pairs into groups of four Next, we merge our pairs together, always comparing the first number of each pair to decide which goes next:
- Merging (2, 7) and (4, 9): Compare 2 vs 4 → 2 goes first. Compare 7 vs 4 → 4 goes next. This gives us 2, 4, 7, 9
- Merging (3, 8) and (1, 5): Compare 3 vs 1 → 1 goes first. Compare 3 vs 5 → 3 goes next. This gives us 1, 3, 5, 8
Step 4: Final merge Finally, we merge our two groups of four into the complete sorted list:
We compare the first numbers of each group (2 vs 1), then continue comparing and adding the smallest available number each time. The result is: 1, 2, 3, 4, 5, 7, 8, 9
Key characteristics of merge sort
Important insight: At every stage of merging, each individual list is always kept in sorted order. This means we only ever need to compare the first numbers of each list we're merging - we never need to look at the other numbers!
This is what makes merge sort so efficient. While bubble sort might need to make hundreds of comparisons and swaps, merge sort organises its work much more cleverly.
Merge sort pseudocode
Here's how we might write merge sort in pseudocode:
REPEAT
Divide each list in half
UNTIL each list is of size 1
REPEAT
REPEAT
REPEAT
Compare the first value in both lists
Insert larger of two values into new merged list
Remove value from old list
UNTIL all numbers in pairs of lists are merged
UNTIL each pair of lists have been considered
UNTIL all lists are merged
Notice how the pseudocode reflects the two main stages: first dividing the data, then systematically merging it back together.
Comparing sorting algorithms
Both bubble sort and merge sort will give you a sorted list, but they work very differently:
- Bubble sort is simple to understand but gets very slow with large lists because it has to make many passes through the data
- Merge sort is much more efficient, especially with large amounts of data, because it's more organised in how it approaches the sorting task
For your GCSE exam, you don't need to memorise the exact pseudocode, but you should understand how these algorithms work and be able to explain their main differences.
Remember!
Key Points to Remember:
- Merge sort uses "divide and conquer" - split the data up, then merge it back together in order
- Every merge results in a sorted list - this is the key to its efficiency
- You only compare the first numbers when merging two sorted lists together
- Merge sort is much more efficient than bubble sort for large amounts of data
- Focus on understanding the process rather than memorising exact pseudocode for your exam