Head to www.savemyexams.
com for more awesome resources
AQA GCSE Computer Science Your notes
Sorting Algorithms
Contents
Merge Sort
Bubble Sort
Comparing Merge Sort & Bubble Sort Algorithms
Page 1 of 10
© 2015-2025 Save My Exams, Ltd. · Revision Notes, Topic Questions, Past Papers
Head to www.savemyexams.com for more awesome resources
Merge Sort
Your notes
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
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?
Example
Perform a merge sort on the following dataset
Page 2 of 10
© 2015-2025 Save My Exams, Ltd. · Revision Notes, Topic Questions, Past Papers
Head to www.savemyexams.com for more awesome resources
Your notes
Examiner Tips and Tricks
In the exam, the divide stage could already be done for you and you would only need to
demonstrate the conquer stage!
A Merge Sort in Python
Page 3 of 10
© 2015-2025 Save My Exams, Ltd. · Revision Notes, Topic Questions, Past Papers
Head to www.savemyexams.com for more awesome resources
# List of numbers to perform merge sort on
numbers = [7, 4, 1, 2, 6, 3, 8, 5] Your notes
# Merge function to merge two sorted lists
def merge(left, right):
merged = []
left_index, right_index = 0, 0
# Merge the two sorted lists
while left_index < len(left) and right_index < len(right):
if left[left_index] < right[right_index]:
merged.append(left[left_index])
left_index += 1
else:
merged.append(right[right_index])
right_index += 1
# Append remaining elements from left or right sublist if there are any remaining elements in the left sublist
while left_index < len(left):
merged.append(left[left_index])
left_index += 1
# If there are any remaining elements in the right sublist
while right_index < len(right):
merged.append(right[right_index])
right_index += 1
return merged
Page 4 of 10
© 2015-2025 Save My Exams, Ltd. · Revision Notes, Topic Questions, Past Papers
Head to www.savemyexams.com for more awesome resources
# Merge sort implementation without using a separate function
Your notes
def merge_sort(arr):
# Checks to see if the list has 1 or 0 elements, it's already sorted
if len(arr) <= 1:
return arr
# Split the list into two halves
mid = len(arr) // 2
left_half = merge_sort(arr[:mid]) # Split and recursively sort left half
right_half = merge_sort(arr[mid:]) # Split and recursively sort right half
# Merge the sorted halves
return merge(left_half, right_half)
# Perform merge sort
sorted_numbers = merge_sort(numbers)
print("Sorted numbers:", sorted_numbers)
Page 5 of 10
© 2015-2025 Save My Exams, Ltd. · Revision Notes, Topic Questions, Past Papers
Head to www.savemyexams.com for more awesome resources
Bubble Sort
Your notes
Bubble Sort
What is a bubble sort?
A bubble sort is a simple sorting algorithm that starts at the beginning of a dataset and checks values in
'pairs' and swaps them if they are not in the correct order
One full run of comparisons from beginning to end is called a 'pass', a bubble sort may require multiple
'passes' to sort the dataset
The algorithm is finished when there are no more swaps to make
How do you perform a bubble sort?
Step Instruction
1 Compare the first two values in the dataset
2 IF they are in the wrong order...
Swap them
3 Compare the next two values
4 REPEAT step 2 & 3 until you reach the end of the dataset (pass 1)
5 IF you have made any swaps...
REPEAT from the start (pass 2,3,4...)
6 ELSE you have not made any swaps...
STOP! the list is in the correct order
Example
Perform a bubble sort on the following dataset
5 2 4 1 6 3
Page 6 of 10
© 2015-2025 Save My Exams, Ltd. · Revision Notes, Topic Questions, Past Papers
Head to www.savemyexams.com for more awesome resources
Step Instruction
Your notes
1 Compare the first two values in the dataset
5 2 4 1 6 3
2 IF they are in the wrong order...
Swap them
2 5 4 1 6 3
3 Compare the next two values
2 5 4 1 6 3
4 REPEAT step 2 & 3 until you reach the end of the dataset
5 & 4 SWAP!
2 4 5 1 6 3
5 & 1 SWAP!
2 4 1 5 6 3
5 & 6 NO SWAP!
2 4 1 5 6 3
6 & 3 SWAP!
2 4 1 5 3 6
End of pass 1
Page 7 of 10
© 2015-2025 Save My Exams, Ltd. · Revision Notes, Topic Questions, Past Papers
Head to www.savemyexams.com for more awesome resources
5 IF you have made any swaps...
REPEAT from the start Your notes
End of pass 2 (swaps made)
2 1 4 3 5 6
End of pass 3 (swaps made)
1 2 3 4 5 6
End of pass 4 (no swaps)
1 2 3 4 5 6
6 ELSE you have not made any swaps...
STOP! the list is in the correct order
Examiner Tips and Tricks
In the exam you do not have to show every swap that takes place in a bubble sort. You can show the
outcome of a bubble sort at the end of each pass. If you have the outcome of each pass correct
then a bubble sort has been implemented correctly and all marks will be given!
Worked Example
A program uses a file to store a list of words.
A sample of this data is shown
Milk Eggs Bananas Cheese Potatoes Grapes
Show the stages of a bubble sort when applied to data shown [2]
Page 8 of 10
© 2015-2025 Save My Exams, Ltd. · Revision Notes, Topic Questions, Past Papers
Head to www.savemyexams.com for more awesome resources
How to answer this question
We need to sort the values in to alphabetical order from A-Z Your notes
You CAN use the first letter of each word to simplify the process
Answer
E, B, C, M, G, P (pass 1)
B, C, E, G, M, P (pass 2)
A bubble sort in python
# unsorted dataset
nums=[66, 7, 69, 50, 42, 80, 71, 321, 67, 8, 39]
# count the length of the dataset
numlength = len(nums)
# sets a flag to initiate the loop
swaps = True
while swaps == True :
swaps = False
# loop through the dataset
for y in range(numlength-1) :
# if the first number is bigger than the second number
if nums[y] > nums[y+1] :
# swap the numbers using a temporary variable
temp = nums[y]
nums[y] = nums[y+1]
nums[y+1] = temp
# sets the flag to true
swaps = True
# prints the sorted list
print (nums)
Page 9 of 10
© 2015-2025 Save My Exams, Ltd. · Revision Notes, Topic Questions, Past Papers
Head to www.savemyexams.com for more awesome resources
Comparing Merge Sort & Bubble Sort Algorithms
Your notes
Comparing Merge Sort & Bubble Sort Algorithms
What are the advantages and disadvantages of a merge sort
and a bubble sort?
Sorting Advantages Disadvantages
Algorithm
Merge sort Suitable for large datasets Uses a lot of memory
Performs well no matter how More complex to implement
unorganised the data is
Bubble sort Simple to understand and implement Slow for large datasets
Inefficient, as it iterates through the
data multiple times
Page 10 of 10
© 2015-2025 Save My Exams, Ltd. · Revision Notes, Topic Questions, Past Papers
