Comparing Sorting Algorithms

This lesson compares the three standard sorting algorithms — bubble sort, merge sort, and insertion sort — as required by OCR J277 Section 2.2. The OCR GCSE Computer Science exam frequently asks students to compare these algorithms, evaluate their efficiency, and recommend the most appropriate one for a given scenario.

---

The Three Sorting Algorithms at a Glance

Feature	Bubble Sort	Insertion Sort	Merge Sort
How it works	Swaps adjacent elements	Inserts into sorted portion	Divide and conquer
Best case	O(n)	O(n)	O(n log n)
Worst case	O(n²)	O(n²)	O(n log n)
Average case	O(n²)	O(n²)	O(n log n)
Space complexity	O(1) — in place	O(1) — in place	O(n) — extra memory
Stable?	Yes	Yes	Yes
Adaptive?	Yes (with flag)	Yes (naturally)	No

OCR Exam Tip: Learn this comparison table. A common 4–6 mark question asks you to compare two or three of these algorithms. Always address time complexity, space complexity, and suitability for different data sizes.

---

Time Complexity Explained

Time complexity describes how the number of operations grows as the dataset gets larger. It is expressed using Big-O notation.

Notation	Name	Description
O(1)	Constant	Does not change with input size
O(n)	Linear	Grows in proportion to input size
O(n²)	Quadratic	Grows as the square of input size
O(n log n)	Linearithmic	Between linear and quadratic
O(log n)	Logarithmic	Grows very slowly

For sorting:

n (items)	O(n²) operations	O(n log n) operations
10	100	~33
100	10,000	~664
1,000	1,000,000	~9,966
10,000	100,000,000	~132,877

This table clearly shows why merge sort (O(n log n)) is dramatically faster than bubble sort and insertion sort (O(n²)) for large datasets.

---

Space Complexity Explained

Space complexity describes how much additional memory an algorithm needs beyond the original data.

• Bubble sort and insertion sort sort in place — they only need a few extra variables (O(1) extra space). They rearrange the data within the original list.
• Merge sort requires additional memory proportional to the size of the list (O(n) extra space) because it creates new sub-lists during the divide and merge phases.

OCR Exam Tip: If a question mentions "limited memory" or a device with "small storage", this is a hint to choose bubble sort or insertion sort over merge sort, because merge sort needs extra memory.

---

Best Case vs Worst Case

Understanding when each algorithm performs at its best or worst is crucial: