Searching and Sorting Algorithms | OCR H446

Learning Objectives

By the end of this topic you will be able to:

Describe and trace linear search and binary search

Describe and trace bubble sort, insertion sort and merge sort

Compare sorting and searching algorithms using Big O notation

Justify algorithm choice for given scenarios

Searching

Linear Search vs Binary Search

Linear Search

Check each element from the start until the target is found or all elements checked.

Works on: unsorted or sorted lists
Time: O(n) worst case
Use when: list is small or unsorted

Binary Search

Compare with middle element. If target is less, search left half; if greater, search right half. Repeat on the relevant half.

Requires: sorted list
Time: O(log n)
Use when: list is sorted and large

Binary search example: find 35 in [10,20,25,30,35,40,50]. Mid=30. 35>30 → search right [35,40,50]. Mid=40. 35<40 → search left [35]. Found. 3 comparisons vs up to 7 for linear.

Bubble Sort

Repeatedly compare adjacent elements and swap if out of order. Each pass bubbles the largest unsorted element to the correct position. Repeat until no swaps occur.

Start: [5, 3, 8, 1, 4]

Pass 1: [3,5,8,1,4]→[3,5,8,1,4]→[3,5,1,8,4]→[3,5,1,4,8]

Pass 2: [3,5,1,4,8]→[3,1,5,4,8]→[3,1,4,5,8]

Pass 3: [1,3,4,5,8] — sorted ✓

Time complexity: O(n²) worst and average case. Suitable only for small datasets. Best case O(n) if optimised to detect no swaps occurred.

Insertion & Merge Sort

Insertion Sort and Merge Sort

Insertion Sort

Build a sorted sublist by taking each element and inserting it into the correct position. Efficient for nearly-sorted data.
Time: O(n²) worst, O(n) best (nearly sorted)

Merge Sort

Divide list in half repeatedly until single elements. Merge pairs in sorted order. Efficient and consistent.
Time: O(n log n) always. Space: O(n) extra memory.
Recursive — naturally maps to a BST traversal.

Merge sort is always O(n log n) — significantly better than O(n²) for large n. At n=1,000,000: merge sort ≈ 20M operations; bubble sort ≈ 10¹² operations.

Big O Summary

Algorithm Complexity Summary

Algorithm	Best	Average	Worst	Space
Linear Search	O(1)	O(n)	O(n)	O(1)
Binary Search	O(1)	O(log n)	O(log n)	O(1)
Bubble Sort	O(n)*	O(n²)	O(n²)	O(1)
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)

*Bubble sort optimised best case. Binary search requires sorted data — the cost of sorting must be considered if the list is unsorted.

Exam Practice

OCR H446 Style · 4 marks

A programmer needs to search a list of 1,000,000 records. The list is already sorted. Compare linear search and binary search for this task and justify which is more appropriate.

[4 marks]

Linear search checks each element sequentially — worst case 1,000,000 comparisons (O(n)). It does not exploit the sorted order.

Binary search halves the search space each step — worst case only log₂(1,000,000) ≈ 20 comparisons (O(log n)).

Since the list is already sorted, binary search can be applied without any additional sorting cost.

Recommendation: binary search — 20 comparisons vs up to 1,000,000. For large sorted datasets, binary search is far more efficient.

Common Mistakes

Don't Lose Marks

Applying binary search to an unsorted list — binary search only works on sorted data. If the list is unsorted, you must sort it first or use linear search. This is a fundamental precondition.

Saying bubble sort is O(n) in general — O(n) only applies to the optimised best case when the list is already sorted (no swaps detected in first pass). The average and worst case are both O(n²). State this qualification.

Forgetting merge sort uses extra memory — merge sort has O(n) space complexity because it creates temporary arrays during merging. Bubble and insertion sort are in-place (O(1) space). This trade-off matters when memory is limited.

Searching & SortingAlgorithms