EnglandComputer ScienceSyllabus dot point

How do bubble, insertion, merge and quick sort order a list, and why are the divide-and-conquer sorts faster?

Sorting algorithms: bubble sort, insertion sort, merge sort and quick sort, how each works with a trace, and their time complexity in Big-O notation including best, average and worst cases.

An OCR H446 answer on sorting algorithms: how bubble sort, insertion sort, merge sort and quick sort order a list with worked traces, and their time complexity in Big-O notation including the difference between the quadratic and the divide-and-conquer sorts.

Generated by Claude Opus 4.814 min answerUpdated 2026-06-02

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Quick answer

Bubble sort repeatedly compares adjacent items and swaps them if out of order, so the largest "bubbles" to the end each pass; it is simple but $O(n^2)$ . Insertion sort builds a sorted section one item at a time, inserting each new item into its correct place; also $O(n^2)$ , but efficient on small or nearly sorted lists. Merge sort uses divide and conquer: split the list into halves recursively until each sublist has one item, then merge sorted sublists back together; it is $O(n \log n)$ in all cases but needs extra memory for the merges. Quick sort picks a pivot, partitions items into those smaller and larger than it, then recursively sorts each partition; it averages $O(n \log n)$ but degrades to $O(n^2)$ with a poor pivot. The divide-and-conquer sorts ( $O(n \log n)$ ) are far faster than the quadratic sorts on large lists.

Jump to a section

What this dot point is asking
The answer
Examples in context
Try this

What this dot point is asking

OCR wants you to describe and trace bubble sort, insertion sort, merge sort and quick sort, and give their time complexities, distinguishing the quadratic sorts from the divide-and-conquer sorts. Expect to trace a pass of a sort and to compare complexities.

The answer

Bubble sort and insertion sort

Merge sort

Quick sort

Trace one pass of insertion sort

Sort $[7, 3, 9, 4]$ with insertion sort, showing how the sorted section grows.

step 1: Start with the first element sorted

The sorted section is just $[7]$ ; the rest is unsorted.

step 2: Insert 3

Compare 3 with 7. Since $3 < 7$ , shift 7 right and place 3 before it: $[3, 7, 9, 4]$ . Sorted section: $[3, 7]$ .

step 3: Insert 9

Compare 9 with 7. Since $9 > 7$ , it is already in place: $[3, 7, 9, 4]$ . Sorted section: $[3, 7, 9]$ .

step 4: Insert 4

Compare 4 with 9 (shift right), then with 7 (shift right), then with 3 ( $4 > 3$ , stop) and place it: $[3, 4, 7, 9]$ . The list is sorted. Insertion sort grew the sorted section one item at a time; on a nearly sorted list few shifts are needed, which is why it is near $O(n)$ then.

Examples in context

Insertion sort is used inside hybrid sorts (like Timsort) for small runs because it is fast on nearly sorted data. Merge sort suits very large datasets and external sorting because its merges stream data, and it is stable. Quick sort is the default in many libraries for its speed and in-place operation, with safeguards on pivot choice. Bubble sort is mainly a teaching example. OCR pairs this with searching (sort once, search many times with binary search) and with Big-O analysis.

Try this

Q1. State the worst-case time complexity of bubble sort and of merge sort. [2 marks]

Cue. Bubble sort $O(n^2)$ ; merge sort $O(n \log n)$ .

Q2. State what quick sort does after choosing a pivot. [2 marks]

Cue. It partitions the list into items smaller than the pivot (to its left) and larger (to its right), then recursively sorts each partition.

Q3. State one situation where insertion sort performs close to $O(n)$ . [1 mark]

Cue. When the list is already sorted or nearly sorted (few shifts are needed).

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 20206 marksUsing the list

[5, 2, 8, 1]

, show one complete pass of a bubble sort with a trace, and state the worst-case time complexity of bubble sort.

Show worked answer →

First pass trace (up to 5), comparing adjacent pairs and swapping if out of order:

comparison	list before	swap?	list after
5 vs 2	$[5, 2, 8, 1]$	yes	$[2, 5, 8, 1]$
5 vs 8	$[2, 5, 8, 1]$	no	$[2, 5, 8, 1]$
8 vs 1	$[2, 5, 8, 1]$	yes	$[2, 5, 1, 8]$

After one pass the largest value (8) has "bubbled" to the end: $[2, 5, 1, 8]$ .

Complexity (1 mark): worst case $O(n^2)$ , because up to $n$ passes each make up to $n$ comparisons. Markers reward a correct adjacent-comparison trace with the largest value moved to the end, and $O(n^2)$ .

OCR 20226 marksExplain how merge sort works using divide and conquer, and explain why its time complexity is

O(n \log n)

rather than

O(n^2)

Show worked answer →

How merge sort works (up to 4): merge sort repeatedly divides the list into two halves until each sublist has one element (which is trivially sorted), then merges pairs of sublists back together in order, comparing the fronts of the two lists and taking the smaller each time, until the whole list is reassembled sorted. It is divide and conquer: split, sort the parts, combine.

Why $O(n \log n)$ (up to 2): the dividing creates about $\log_2 n$ levels of splitting (halving each time), and merging at each level processes all $n$ elements, so the total work is $n$ per level times $\log n$ levels, giving $O(n \log n)$ . This beats the $O(n^2)$ of bubble or insertion sort on large lists. Markers reward split-to-single-then-merge plus the $\log n$ levels times $n$ work argument.

Related dot points

Sources & how we know this

OCR AS and A Level Computer Science (H046, H446) specification — OCR (2015)