Key Terms
- Bubble sort: Repeatedly compares adjacent pairs and swaps them if in the wrong order
- Insertion sort: Builds a sorted portion by taking each element and inserting it into its correct position
- Merge sort: Divides the list in half repeatedly, then merges sorted halves back together
- Pass: One complete run through the list during bubble sort
- Divide and conquer: Strategy of splitting a problem into smaller parts, solving each, then combining results
Must-Know Facts
- Bubble sort: after each pass, the largest unsorted value moves to its final position
- Bubble sort is complete when a full pass produces no swaps
- Insertion sort: good for nearly-sorted data; builds sorted portion one element at a time
- Merge sort uses more memory (creates new arrays) but is much faster for large lists
- Bubble and insertion sort: O(n²) — slow for large lists
- Merge sort: O(n log n) — efficient for large lists
Key Concepts
- Bubble sort: compare neighbours → swap if wrong order → repeat until no swaps
- Insertion sort: take next item → find its correct place in sorted portion → insert
- Merge sort: split → split → split (single elements) → merge in order → merge → merge
- Memory trick: Bubble = big values bubble up; Insertion = insert cards one by one; Merge = split then merge
- In exams: always show the list state after each pass/step
Common Mistakes
- Not showing the list after each pass in bubble sort: Exam questions specifically ask for the state of the list after each pass — showing only the final sorted list loses all method marks
- Stopping bubble sort too early: Bubble sort is only complete when a full pass produces no swaps — stopping after a fixed number of passes gives the wrong answer
- Confusing insertion sort with bubble sort: Bubble sort compares adjacent pairs and swaps them; insertion sort picks each element and inserts it into the correct position in the already-sorted portion
- Saying merge sort is always best: Merge sort is faster for large lists (O(n log n)) but uses more memory — insertion sort can be faster for small or nearly-sorted lists
- Forgetting merge sort needs extra memory: Merge sort creates new sub-arrays during splitting and merging — this memory overhead is a key disadvantage compared to bubble and insertion sort
This topic summary covers Knowledge Organiser: Sorting Algorithms within Binary Search for GCSE Computer Science. Revise Binary Search in 3.1 Fundamentals of Algorithms for GCSE Computer Science with 15 exam-style questions and 10 flashcards. This is a high-frequency topic, so it is worth revising until the explanation feels precise and repeatable. It is section 9 of 9 in this topic. Use this topic summary to connect the idea to the wider topic before moving on to questions and flashcards.
Practice questions for Binary Search
Which of the following is a requirement before binary search can be used?
Describe how a binary search algorithm finds a target value in a sorted list.
Quick recall flashcards
What technique does binary search use?
Divide and conquer - repeatedly halves the search space
What is the time complexity of binary search?
O(log n) - logarithmic time