Merge Sort (AQA GCSE Computer Science)

What is a sorting algorithm?

• Sorting algorithms are precise step-by-step instructions that a computer can follow to efficiently sort data in massive datasets
• Two common sorting algorithms are:
  • Bubble sort
  • Merge sort

What is a merge sort?

• A merge sort is a sorting algorithm that uses the 'divide and conquer' strategy of dividing a dataset into smaller sub-datasets and merging them back together in the correct order

How do you perform a merge sort?

Step	Instruction
1	Divide the dataset into individual datasets by repeatedly splitting the dataset in half (DIVIDE)
2	Merge pairs of sub-datasets together by comparing the first value in each dataset (CONQUER)
3	REPEAT step 2 until all sub-datasets are merged together into one dataset

Example

• Perform a merge sort on the following dataset

7

4

1

2

6

3

8

5

Step	Instruction
1	Divide the dataset into individual datasets by repeatedly splitting the dataset in half (DIVIDE) 7 4 1 2 6 3 8 5 divide in half (2 datasets of 4 values) 7 4 1 2   6 3 8 5 divide in half again (4 datasets of 2 values) 7 4   1 2   6 3   8 5 divide in half again  (8 datasets of 1 value) 7   4   1   2   6   3   8   5
2	Merge pairs of sub-datasets together by comparing the first value in each dataset (CONQUER) 7   4   1   2   6   3   8   5 Merge into 4 datasets of 2 values 4 7   1 2   3 6   5 8
3	REPEAT step 2 until all sub-datasets are merged together into one dataset Merge into 2 datasets of 4 values 1 2 4 7   3 5 6 8 Merge into 1 dataset of 8 values (in the correct order) 1 2 3 4 5 6 7 8