Sorting Algorithms

What a sorting algorithm does

A sorting algorithm puts a list of items into order (usually ascending). At GCSE you need three: bubble sort, merge sort and insertion sort — how each works and their relative speed.

Bubble sort

Bubble sort repeatedly steps through the list, comparing adjacent pairs and swapping them if they're in the wrong order. Large values "bubble" to the end.

Steps (one pass):

1. Compare the first two items; swap if the left is bigger.

2. Move one place right and repeat to the end of the list.

3. After each pass, the next-largest item is in its final place.

4. Repeat passes until a pass makes no swaps → the list is sorted.

Key points:

• Very simple to understand and code.
• Slow on large lists: for n items it makes up to n−1 passes of up to n−1 comparisons.
• Good for spotting an already-sorted list quickly (one clean pass, no swaps).

Insertion sort

Insertion sort builds a sorted section at the start, inserting each new item into its correct position among the already-sorted items.

Steps:

1. Treat the first item as a sorted list of one.

2. Take the next item and compare it backwards through the sorted section.

3. Shift larger items right and insert the item into the gap.

4. Repeat until every item has been inserted.

Key points:

• Efficient for small or nearly-sorted lists.
• Sorts "in place" (no extra list needed).

Merge sort

Merge sort uses divide and conquer: it splits the list down to single items, then merges them back together in order.

Steps:

1. Divide: keep splitting the list in half until every sub-list has one item (a single item is already sorted).

2. Merge: repeatedly combine pairs of sub-lists, each time comparing the fronts and taking the smaller, to build larger sorted lists.

3. Continue merging until one full sorted list remains.

Key points:

• Much faster than bubble/insertion on large lists.
• Uses more memory, because it creates new sub-lists while merging.
• More complex to program (often uses recursion).

Worked example (bubble sort, one pass)

Start: [5, 3, 8, 1]

• Compare 5,3 → swap → [3, 5, 8, 1]
• Compare 5,8 → no swap → [3, 5, 8, 1]
• Compare 8,1 → swap → [3, 5, 1, 8]

After pass 1, 8 is in its final place. More passes finish the sort.

Comparison table

	Bubble	Insertion	Merge
Idea	swap adjacent pairs	insert into sorted part	split then merge
Speed (large lists)	slow	slow–medium	fast
Extra memory	low	low	higher
Best for	teaching / tiny lists	small / nearly sorted	large lists

Common mistakes

• Describing bubble sort without the repeated passes until no swaps.
• Forgetting merge sort's trade-off: fast but uses more memory.
• Saying merge sort "compares adjacent items" — that's bubble sort.

Exam tips

• Learn to trace one pass of bubble sort and show every swap — a common exam task.
• For merge sort, clearly show the split stage and the merge stage separately.
• If asked which is fastest on a big list, the answer is merge sort.

Key facts to remember

• Bubble: swap adjacent pairs over repeated passes; simple but slow.
• Insertion: insert each item into a growing sorted section; good for small/nearly-sorted.
• Merge: divide into single items then merge in order; fastest on large lists but uses more memory.