Merge sort (Edexcel GCSE Computer Science): Revision Notes
Merge sort
What is merge sort?
Merge sort is a powerful sorting algorithm that works by using a "divide and conquer" approach. The technique takes a list of unsorted data and systematically breaks it down into smaller parts, then carefully builds it back up in the correct order.
Think of it like organising a messy deck of cards by first splitting the deck into smaller piles, sorting each pile, then combining them back together in order.
The key principle behind merge sort is that it's much easier to sort small groups of items and then combine them, rather than trying to sort one large group all at once.
How merge sort works
Merge sort follows a clear 4-step process that repeats until the list is completely sorted:
Step 1: Divide the list
The algorithm starts by breaking the original list into two halves, then continues dividing each half into smaller halves. This process continues until each "list" contains only a single item.
Example: Dividing the List [6, 3, 5, 1, 8, 2, 4, 7]
First division: [6, 3, 5, 1] and [8, 2, 4, 7]
Second division: [6, 3], [5, 1], [8, 2], [4, 7]
Final division: [6], [3], [5], [1], [8], [2], [4], [7]
Step 2: Sort pairs in ascending order
Now that each item is in its own list, we start comparing and merging pairs back together. At this stage, we compare the individual items and put them in the correct order.
[3, 6], [1, 5], [2, 8], [4, 7]
Notice how 3 comes before 6, 1 comes before 5, and so on.
Step 3: Merge pairs of lists
The next step involves comparing the first items from each pair of sorted lists. We take the smaller item and add it to our new combined list, then continue comparing until both lists are merged.
Example: Merging [3, 6] and [1, 5]
Step-by-step process:
- Compare 3 and 1: 1 is smaller, so it goes first
- Compare 3 and 5: 3 is smaller, so it goes next
- Compare 6 and 5: 5 is smaller, so it goes next
- 6 goes last
Result: [1, 3, 5, 6] and [2, 4, 7, 8]
Step 4: Final merge
Finally, we combine the two remaining sorted lists using the same comparison method to create one completely sorted list.
The final result is: [1, 2, 3, 4, 5, 6, 7, 8]
Worked example
Worked Example: Understanding the Merge Sort Process
Question: Describe how data is sorted into ascending order using the merge sort algorithm.
Answer: The merge sort process works by repeatedly dividing the list into halves until each section contains only one item. Then, these individual items are progressively merged back together, with comparisons made at each step to ensure the items are placed in ascending order.
The key advantage of this approach is that by breaking the problem down into smaller parts, the sorting becomes much more manageable and efficient.
Why use merge sort?
Merge sort has several important advantages, especially when dealing with large amounts of data:
- Efficiency: For large numbers of items, merge sort is far more efficient than simpler algorithms like bubble sort
- Predictable performance: It consistently performs well regardless of how the original data is arranged
- Divide and conquer: By breaking the problem down into smaller, easier-to-solve pieces, it makes sorting manageable even for very large datasets
This makes merge sort particularly useful in real-world applications where you need to sort thousands or millions of items quickly and reliably.
Practice question
Practice Challenge
Try this yourself: Create a diagram showing the steps needed to sort the list [38, 27, 43, 3, 9, 82, 10] into ascending order using merge sort.
Hint: Start by dividing the list in half, keep dividing until you have individual items, then merge them back together in order!
Remember!
Key Points to Remember:
- Merge sort uses divide and conquer - break the problem into smaller pieces
- The process has 4 main steps: divide, divide again, merge pairs, final merge
- Individual items are always considered "sorted" - that's why we divide down to single items
- Comparisons happen during the merging process, not the dividing process
- Merge sort is much more efficient than bubble sort for large datasets because it reduces the number of comparisons needed