Searching and sorting algorithms — OCR GCSE Computer Science
Teaching note checked against the official specification.
Test yourself on Searching and sorting algorithms with OCR GCSE practice questions.
A week of Premium from your first lesson · Then the free plan continues · No card, no charge
Searching and sorting algorithms explained
Searching and sorting algorithms covers 2 specification points, including Standard searching algorithms Binary search… and Standard sorting algorithms Bubble sort Merge….
Read the full explanation
Open a point below for its explanation and revision guidance.
Standard searching algorithms Binary search Linear search
A searching algorithm locates a target value within a data structure and reports its position or confirms absence. Linear search inspects each item in turn from the start until the target is found or the list ends; it works on any list, sorted or not, and is simple but slow on large data. Binary search requires a sorted list: it examines the middle item, then discards the half that cannot contain the target, repeating on the remaining half. Each comparison halves the search space, so binary search is far faster on large sorted lists. For example, searching for 23 in [4, 9, 15, 23, 31, 42, 57]: check the middle 23 and stop. Linear search would check 4, 9, 15 then 23.
Standard sorting algorithms Bubble sort Merge sort Insertion sort
Sorting algorithms arrange data into order, usually ascending. Bubble sort repeatedly compares adjacent items and swaps them when out of order, so large values 'bubble' to the end; each pass places one more item correctly, and passes repeat until no swaps occur. Insertion sort builds a sorted section at the start: it takes the next item and inserts it into the correct position among those already sorted, shifting larger items right. Merge sort splits the list into single items, then repeatedly merges pairs of sorted sublists by comparing their front items, producing larger sorted lists until one remains. Bubble and insertion sort are simple and suit small lists; merge sort is more efficient on large lists.
Watch and listen
Listen: Searching and sorting algorithms audio lesson
Read the full guide
Your focus
- Describe the steps of linear search and binary search.
- Apply linear search and binary search to a given list and identify the items examined.
- Compare the two algorithms in terms of data requirements and efficiency on large data sets.
Show all 6 objectives
- Describe how bubble sort, insertion sort and merge sort order a list of data.
- Trace a named sorting algorithm on a given list, showing intermediate stages.
- Compare the suitability of the three algorithms for lists of different sizes.
Searching and sorting algorithms exam tips
Marking Points
- States that linear search checks each element in sequence from the start until the target is found or the end of the list is reached.
- States that binary search requires the data to be sorted before it can be used.
- Describes binary search finding the middle element, comparing it with the target, then discarding the half that cannot contain the target and repeating on the remaining half.
- Explains that binary search is generally more efficient than linear search on large sorted data sets because each comparison halves the remaining search space.
- Identifies that linear search works on unsorted data whereas binary search does not.
- Applies either algorithm to a given list, showing the sequence of items examined and the final result.
- Describes bubble sort comparing adjacent pairs and swapping them when they are in the wrong order, repeating passes until no swaps are needed.
- Describes insertion sort taking each item in turn and inserting it into its correct position within the already sorted section.
- Describes merge sort repeatedly splitting the list into smaller sublists until single items remain, then merging sublists in order.
- Applies a named sorting algorithm to a given list, showing the list after each pass or merge.
- Compares the algorithms, for example noting that merge sort is generally more efficient on large data sets while bubble and insertion sort are simpler to implement.
Examiner Tips
- 💡When tracing a search, write out the list at each stage and cross out the discarded half so the examiner can follow your method.
- 💡If asked to compare the algorithms, refer to the sorted-data requirement and the effect of halving the search space rather than just saying one is faster.
- 💡For a 'describe' question, give the steps in order; for an 'explain' question, link each step to why it reduces the work done.
- 💡Show every pass or merge stage in a trace table or list so the method is visible, not just the final sorted list.
- 💡Use the correct terminology: 'pass', 'swap', 'insert' and 'merge' signal understanding to the examiner.
- 💡When comparing algorithms, refer to the number of comparisons or passes needed as list size grows rather than vague statements about speed.
Common Mistakes
- Believing binary search works on any list: it only works on sorted data, so state the sorting requirement explicitly.
- Thinking binary search always checks the exact middle item of the original list at every stage: after each comparison the search space shrinks, so the middle is recalculated within the remaining sublist.
- Confusing the two algorithms' efficiency: linear search may be faster on very small or unsorted lists, while binary search wins on large sorted lists.
- Stopping bubble sort after one pass: passes continue until a complete pass produces no swaps, because one pass may not fully sort the list.
- Merging sublists by simply joining them: merging compares the front items of each sorted sublist and takes the smaller one first.
- Inserting an item without shifting the larger sorted items to the right, which overwrites values and loses data.