How do bubble sort, insertion sort and merge sort each put a list in order?
Standard sorting algorithms: bubble sort, insertion sort and merge sort, how each works step by step, and how they compare in approach and efficiency.
An OCR J277 2.1.3 answer on the three standard sorting algorithms: how bubble sort, insertion sort and merge sort each put a list in order step by step, and how they compare in method and efficiency.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
Jump to a section
What this dot point is asking
OCR wants you to describe the three standard sorting algorithms, bubble sort, insertion sort and merge sort, step by step, to trace each on a short list, and to compare them by method and efficiency. OCR is one of the few boards that includes insertion sort as well as bubble and merge, so all three must be learned. This is examined in Paper 2, often as a trace or a comparison.
Bubble sort
For the list 5, 3, 8, 1, the first pass compares 5 and 3 (swap), 5 and 8 (no swap), 8 and 1 (swap), giving 3, 5, 1, 8. Further passes sort the rest until no swaps occur.
Insertion sort
Merge sort
For 6, 2, 7, 4: split into (6, 2) and (7, 4); split again into single items; merge 6 and 2 into (2, 6) and 7 and 4 into (4, 7); finally merge (2, 6) and (4, 7) into 2, 4, 6, 7.
Comparing the three
All three produce a correctly sorted list; they differ in method, speed and memory. Bubble and insertion sort are simple, easy to code and use almost no extra memory, but both are slow on large lists. Insertion sort has an edge on small or nearly-sorted data. Merge sort is more complex and uses more memory (the extra sublists), but it scales far better: on large lists it is dramatically faster because splitting and merging grows much more slowly than the repeated passes of bubble or insertion sort. The exam answer is usually: bubble and insertion for simplicity and small data, merge for speed on large data.
Try this
Q1. State what a bubble sort does in a single pass. [1 mark]
- Cue. It compares each adjacent pair from the start and swaps any that are in the wrong order, moving the largest remaining item to the end.
Q2. State the two stages of a merge sort. [2 marks]
- Cue. Split the list repeatedly in half until each part has one item, then merge the parts back together in order.
Q3. Give one advantage of bubble sort and one advantage of merge sort. [2 marks]
- Cue. Bubble sort: simple to understand and code, and uses little memory. Merge sort: much faster (more efficient) on large lists.
Exam-style practice questions
Practice questions written in the style of OCR exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.
OCR 20214 marksShow how one complete pass of a bubble sort would change the list 5, 3, 8, 1. State the list after the pass and the number of swaps made.Show worked answer →
A bubble sort compares each adjacent pair, left to right, and swaps them if they are in the wrong order. Starting 5, 3, 8, 1:
Compare 5 and 3: 5 > 3, swap to give 3, 5, 8, 1. Compare 5 and 8: in order, no swap. Compare 8 and 1: 8 > 1, swap to give 3, 5, 1, 8.
After one pass the list is 3, 5, 1, 8, with 2 swaps made. The largest value, 8, has "bubbled" to the end, which is the correct position after one pass.
Markers reward the correct comparisons, swaps and the list after the pass. A common slip is to fully sort the list rather than show one pass, or to compare non-adjacent items.
OCR 20226 marksCompare bubble sort and merge sort. Your answer should explain how each works and discuss their relative efficiency.Show worked answer →
A 6-mark comparison, so explain each method then compare.
Bubble sort: repeatedly passes through the list comparing adjacent pairs and swapping any in the wrong order, until a pass makes no swaps. It is simple to understand and code, and uses little memory, but it is slow on large lists because it may make many passes and many comparisons.
Merge sort: a divide-and-conquer algorithm. It repeatedly splits the list in half until each part has one item, then merges the parts back together in order. It is much faster on large lists, but it is more complex and uses more memory because it creates additional sublists.
Comparison: merge sort is far more efficient on large lists (it scales much better), while bubble sort is simpler and uses less memory but is very slow on large data. Markers reward how each works (especially split-then-merge for merge sort), and a clear efficiency comparison, ideally noting merge sort's extra memory use.
Related dot points
- Standard searching algorithms: linear search and binary search, how each works step by step, the requirement that binary search needs a sorted list, and the comparison of their efficiency.
An OCR J277 2.1.3 answer on the two standard searching algorithms: how linear search and binary search work step by step, why binary search needs a sorted list, and how their efficiency compares.
- Producing algorithms using pseudocode and flowcharts to solve a problem, identifying the inputs, processes and outputs, and interpreting, correcting and refining algorithms others have written.
An OCR J277 2.1.2 answer on designing algorithms with pseudocode and flowcharts: identifying inputs, processes and outputs, the OCR Exam Reference Language, the standard flowchart symbols, and interpreting, correcting and refining algorithms.
- Using trace tables to determine the output of an algorithm and to follow how the values of variables change, and determining the purpose of a simple algorithm.
An OCR J277 2.1.2 answer on using trace tables to follow an algorithm step by step, record how variable values change, find the output, and determine the purpose of a simple algorithm.
- The principles of computational thinking: abstraction, decomposition and algorithmic thinking, and how each is used to analyse a problem and design a solution.
An OCR J277 2.1.1 answer on the principles of computational thinking: abstraction (removing unnecessary detail), decomposition (breaking a problem into smaller parts) and algorithmic thinking (a clear sequence of steps), with examples of how each is applied to a problem.
- Using one-dimensional and two-dimensional arrays, the use of records to store structured data, and basic SQL (SELECT, FROM, WHERE) to search records in a database.
An OCR J277 2.2.3 answer on storing structured data: one-dimensional and two-dimensional arrays, records, and using basic SQL (SELECT, FROM, WHERE) to search records in a database table.
Sources & how we know this
- OCR GCSE (9-1) Computer Science (J277) specification — OCR (2020)