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.
Knowledge Organiser: Sorting Algorithms
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
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