You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
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.
| 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 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 describes how much additional memory an algorithm needs beyond the original data.
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.
Understanding when each algorithm performs at its best or worst is crucial:
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.