EnglandComputer ScienceSyllabus dot point

How do bubble, insertion, merge and quick sort work, and which is most efficient?

Sorting algorithms: bubble sort and insertion sort and their quadratic efficiency, merge sort and quick sort and their use of divide and conquer, and comparing sorting algorithms by time complexity and stability.

An Eduqas Component 1 answer on sorting: how bubble and insertion sort work and why they are quadratic, how merge sort and quick sort use divide and conquer to reach n log n, and comparing the algorithms by time complexity.

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 steps through the list, comparing adjacent pairs and swapping any that are out of order, so the largest value "bubbles" to the end each pass; it is simple but $O(n^2)$ . Insertion sort builds a sorted section at the front, taking each new element and inserting it into its correct place among those already sorted; it is also $O(n^2)$ but efficient on nearly sorted data. Both are in-place (little extra memory) and easy to code. Merge sort uses divide and conquer: split the list in half repeatedly until sublists have one element, then merge sorted sublists back together; this gives $O(n \log n)$ but needs extra memory for the merges. Quick sort picks a pivot, partitions the list into items smaller and larger than the pivot, then recursively sorts each part; it averages $O(n \log n)$ , is usually in-place, but degrades to $O(n^2)$ with a poor pivot. For large data the $O(n \log n)$ algorithms win decisively.

Jump to a section

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

What this dot point is asking

Eduqas wants you to describe bubble sort and insertion sort and explain why they are quadratic, describe merge sort and quick sort and their divide-and-conquer strategy, and compare the algorithms by time complexity. Sorting questions usually ask for a trace of one pass plus a complexity justification.

The answer

Bubble sort and insertion sort

Merge sort

Quick sort

Examples in context

Sorting underlies almost everything: arranging search results, ordering a leaderboard, or preparing data for a binary search (which needs sorted input). For small or nearly sorted lists, insertion sort is genuinely efficient; for large data, library routines use $O(n \log n)$ algorithms (often a quick sort or a hybrid). The divide-and-conquer idea in merge sort and quick sort reappears in the next dot point on recursion and Big-O, which formalises why halving the problem produces the $\log n$ factor.

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. Give one advantage of insertion sort over bubble sort. [1 mark]

Cue. It is efficient ( $O(n)$ ) on data that is already nearly sorted, since few shifts are needed.

Q3. Why can quick sort degrade to $O(n^2)$ ? [1 mark]

Cue. A poorly chosen pivot (for example always the smallest element) gives very unbalanced partitions, so the recursion depth grows to $n$ .

Exam-style practice questions

Practice questions written in the style of WJEC Eduqas exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

Eduqas 20195 marksThe list

[5, 2, 8, 1, 9, 3]

is to be sorted into ascending order using a bubble sort. Show the list after the first complete pass, and explain why bubble sort has a worst-case time complexity of

O(n^2)

Show worked answer →

First pass (up to 3 marks): compare and swap adjacent out-of-order pairs left to right. $5,2 \to$ swap; $5,8 \to$ no swap; $8,1 \to$ swap; $8,9 \to$ no swap; $9,3 \to$ swap. After one pass: $[2, 5, 1, 8, 3, 9]$ , with the largest value $9$ bubbled to the end.

Complexity (up to 2 marks): there are up to $n - 1$ passes, each making up to $n - 1$ comparisons, so the work grows with $n \times n = n^2$ , giving $O(n^2)$ .

Markers reward the correct list after one pass (largest at the end) and the nested-pass reasoning for $O(n^2)$ .

Eduqas 20216 marksExplain how merge sort uses a divide-and-conquer approach to sort a list, and state its time complexity. Give one advantage and one disadvantage compared with bubble sort.

Show worked answer →

Divide and conquer (up to 3 marks): merge sort repeatedly splits the list in half until each sublist has one element (which is trivially sorted), then merges pairs of sorted sublists back together in order, repeating until one sorted list remains.

Complexity (up to 1 mark): the splitting gives $\log n$ levels and each merge level does $O(n)$ work, so merge sort is $O(n \log n)$ .

Comparison (up to 2 marks): advantage, far faster than bubble sort's $O(n^2)$ on large lists; disadvantage, it needs extra memory for the temporary sublists, whereas bubble sort sorts in place.

Markers reward the split-then-merge description, the $O(n \log n)$ complexity, and a valid advantage and disadvantage.

Related dot points

Sources & how we know this

WJEC Eduqas GCE AS/A Level Computer Science specification (from 2015) — Eduqas (2015)