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:

Algorithm	Best Case Scenario	Worst Case Scenario
Bubble sort	Data already sorted — one pass, no swaps, O(n)	Data in reverse order — maximum passes and swaps, O(n²)
Insertion sort	Data already sorted — each element needs only one comparison, O(n)	Data in reverse order — each element must shift through entire sorted portion, O(n²)
Merge sort	Always O(n log n) regardless of initial order	Always O(n log n) — consistent performance

A key advantage of merge sort is its consistent performance — it always takes O(n log n) time, regardless of whether the data is sorted, random, or reversed. Bubble sort and insertion sort can be very fast on nearly-sorted data but extremely slow on reversed data.

---

Choosing the Right Algorithm

Scenario 1: Small Dataset, Nearly Sorted

Best choice: Insertion sort Reason: With nearly sorted data, insertion sort runs in nearly O(n) time and has very low overhead.

Scenario 2: Large Dataset, Random Order

Best choice: Merge sort Reason: O(n log n) is dramatically faster than O(n²) for large datasets, and the order of the data does not affect merge sort's performance.

Scenario 3: Limited Memory Available

Best choice: Bubble sort or insertion sort Reason: Both sort in place with O(1) extra space, whereas merge sort needs O(n) extra space.

Scenario 4: Data in Completely Random Order, Medium Size

Best choice: Merge sort (or insertion sort if memory is constrained) Reason: For medium to large datasets, merge sort's O(n log n) is reliable.

---

Exam-Style Worked Example

Question: A teacher needs to sort 50,000 student exam results. The data is currently in random order. Compare the suitability of merge sort and bubble sort for this task. (4 marks)

Answer:

• Merge sort would be more suitable because it has a time complexity of O(n log n), meaning approximately 50,000 × 17 ≈ 850,000 operations. Bubble sort has a worst case of O(n²), meaning up to 2,500,000,000 operations — approximately 3,000 times slower.
• However, merge sort requires additional memory of O(n) to store sub-lists during sorting, whereas bubble sort sorts in place with O(1) extra memory.
• Given 50,000 records, the time saving of merge sort far outweighs its extra memory usage.
• Therefore, merge sort is the better choice for this large, randomly ordered dataset.

---

Summary

• Bubble sort and insertion sort are O(n²) in the worst/average case but O(n) in the best case.
• Merge sort is consistently O(n log n) but requires O(n) extra memory.
• For small or nearly-sorted data: insertion sort is often best.
• For large datasets: merge sort is usually best.
• For memory-constrained systems: in-place algorithms (bubble/insertion) are preferred.

OCR Exam Tip: When comparing algorithms in the exam, always structure your answer around: (1) time complexity, (2) space complexity, and (3) suitability for the given scenario. This framework ensures you cover all the key points.

---

Algorithm Selection Flowchart

flowchart TD
    A([Start: choose a sorting algorithm]) --> B{Dataset size?}
    B -- Small < 50 --> C{Data nearly sorted?}
    C -- Yes --> D[Insertion sort]
    C -- No --> E[Insertion or bubble sort]
    B -- Large >= 50 --> F{Memory constrained?}
    F -- Yes --> G[Insertion sort]
    F -- No --> H{Worst case matters?}
    H -- Yes --> I[Merge sort]
    H -- No --> I

This decision tree captures the standard exam-ready reasoning. Memorise it — it will help you answer "which sort should be used?" questions quickly.

---

Numerical Comparison: Running Time for Different n

Assume a computer performs 10⁸ (100 million) operations per second. Here is an approximate comparison of how long each algorithm would take in the worst case:

n	Bubble/Insertion (O(n²))	Merge (O(n log n))
100	10,000 ops ≈ 0.0001 s	~664 ops, negligible
1,000	1,000,000 ops ≈ 0.01 s	~9,966 ops, negligible
10,000	100,000,000 ops ≈ 1 s	~132,877 ops ≈ 0.0013 s
100,000	10,000,000,000 ops ≈ 100 s	~1,660,964 ops ≈ 0.017 s
1,000,000	10¹² ops ≈ 10,000 s (2.8 hours)	~20,000,000 ops ≈ 0.2 s

This shows dramatically how O(n²) algorithms become unusable for large data, while O(n log n) algorithms remain practical.

---

Key Terms in Algorithm Analysis