Algorithms: Searching and Sorting

What you'll learn

This revision guide covers searching and sorting algorithms that appear in the WJEC GCSE Computer Science specification. You'll master how linear and binary search locate data, understand bubble sort and merge sort implementations, and learn to evaluate algorithm efficiency. These algorithms form essential exam content worth substantial marks.

Key terms and definitions

Algorithm — A finite sequence of precise, step-by-step instructions designed to solve a problem or perform a task.

Linear search — A searching algorithm that examines each item in a list sequentially from start to finish until the target is found or the list ends.

Binary search — A searching algorithm that repeatedly divides a sorted list in half, comparing the middle element with the target value to eliminate half the remaining data.

Bubble sort — A sorting algorithm that repeatedly steps through a list, comparing adjacent elements and swapping them if they are in the wrong order.

Merge sort — A divide-and-conquer sorting algorithm that recursively splits a list into halves, sorts them separately, then merges the sorted halves.

Efficiency — A measure of how well an algorithm performs in terms of time (number of operations) and space (memory usage).

Iteration — A single pass through a loop or repetitive process within an algorithm.

Comparison — An operation where two data values are examined to determine their relative order or equality.

Core concepts

Linear search

Linear search works through a list from the beginning, checking each element in turn until the target item is found or the end is reached.

How linear search works:

1. Start at the first element in the list
2. Compare the current element with the target value
3. If they match, return the position and stop
4. If they don't match, move to the next element
5. Repeat steps 2-4 until the target is found or the list ends
6. If the list ends without finding the target, return "not found"

Advantages of linear search:

• Works on unsorted and sorted lists
• Simple to understand and implement
• Efficient for small datasets
• No data preparation required

Disadvantages of linear search:

• Inefficient for large datasets
• Must check every element in worst-case scenario (target not present)
• Time increases directly with list size

Efficiency: In the worst case, linear search must examine all n elements. For a list of 1000 items, up to 1000 comparisons may be needed.

Binary search

Binary search is significantly faster than linear search but requires the list to be sorted first. It eliminates half the remaining data with each comparison.

How binary search works:

1. Find the middle element of the sorted list
2. Compare the middle element with the target value
3. If they match, return the position and stop
4. If the target is smaller, repeat the search on the left half
5. If the target is larger, repeat the search on the right half
6. Continue until the target is found or the search space is empty
7. If the search space becomes empty, return "not found"

Example trace: Searching for 37 in [12, 18, 25, 37, 42, 51, 68, 79]

• First check: Middle element is 37 (position 3) — found!

Searching for 68 in the same list:

• First check: Middle element is 37 — target larger, search right half [42, 51, 68, 79]
• Second check: Middle element is 51 — target larger, search right half [68, 79]
• Third check: Middle element is 68 — found!

Advantages of binary search:

• Much faster than linear search for large datasets
• Efficiency increases dramatically as data size grows
• Predictable maximum number of comparisons

Disadvantages of binary search:

• Only works on sorted lists
• Requires extra processing if data isn't already sorted
• More complex to implement than linear search

Efficiency: Binary search needs at most log₂(n) comparisons. For 1000 items, only about 10 comparisons are required (compared to 1000 for linear search).

Bubble sort

Bubble sort is a simple sorting algorithm that repeatedly passes through a list, comparing adjacent elements and swapping them if they're in the wrong order. Larger values "bubble" to the end.

How bubble sort works:

1. Start at the beginning of the list
2. Compare the first two adjacent elements
3. If they are in the wrong order, swap them
4. Move to the next pair of adjacent elements
5. Repeat steps 2-4 until the end of the list
6. After one complete pass, the largest value is in the correct position
7. Repeat the entire process for the remaining unsorted portion
8. Continue until no swaps are made in a complete pass

Example trace: Sorting [64, 34, 25, 12] in ascending order

Pass 1:

• Compare 64 and 34: swap → [34, 64, 25, 12]
• Compare 64 and 25: swap → [34, 25, 64, 12]
• Compare 64 and 12: swap → [34, 25, 12, 64]

Pass 2:

• Compare 34 and 25: swap → [25, 34, 12, 64]
• Compare 34 and 12: swap → [25, 12, 34, 64]

Pass 3:

• Compare 25 and 12: swap → [12, 25, 34, 64]
• No more swaps needed for remaining pairs

Pass 4:

• No swaps made → list is sorted

Advantages of bubble sort:

• Simple to understand and code
• Works well for small datasets
• Efficient if data is already nearly sorted
• Requires minimal additional memory

Disadvantages of bubble sort:

• Very inefficient for large datasets
• Makes many unnecessary comparisons
• Much slower than advanced sorting algorithms

Efficiency: Bubble sort makes approximately n² comparisons in the worst case. For 1000 items, this means about 1,000,000 comparisons.

Merge sort

Merge sort is a more sophisticated divide-and-conquer algorithm that splits a list into smaller sublists, sorts them, then merges them back together in order.

How merge sort works:

1. Divide the unsorted list into n sublists, each containing one element
2. Repeatedly merge sublists to produce sorted sublists
3. During merging, compare the first elements of each sublist
4. Take the smaller element and add it to the result
5. Continue comparing and merging until all elements are in one sorted list

Example trace: Sorting [38, 27, 43, 3]

Divide phase:

• [38, 27, 43, 3] → split → [38, 27] and [43, 3]
• [38, 27] → split → [38] and [27]
• [43, 3] → split → [43] and [3]

Merge phase:

• Merge [38] and [27] → [27, 38]
• Merge [43] and [3] → [3, 43]
• Merge [27, 38] and [3, 43] → [3, 27, 38, 43]

Merging detail for final step:

• Compare 27 and 3: take 3 → [3]
• Compare 27 and 43: take 27 → [3, 27]
• Compare 38 and 43: take 38 → [3, 27, 38]
• Only 43 remains → [3, 27, 38, 43]

Advantages of merge sort:

• Much more efficient than bubble sort for large datasets
• Consistent performance regardless of initial order
• Stable sort (maintains relative order of equal elements)
• Predictable execution time

Disadvantages of merge sort:

• Requires additional memory for temporary storage
• More complex to understand and implement
• Overkill for small datasets

Efficiency: Merge sort makes approximately n log₂(n) comparisons. For 1000 items, about 10,000 comparisons are needed — far fewer than bubble sort's 1,000,000.

Comparing algorithm efficiency

Understanding when to use each algorithm is crucial for GCSE exam questions.

Search algorithm comparison:

Algorithm	Data requirement	Small dataset	Large dataset	Comparisons (1000 items)
Linear search	Any order	Acceptable	Slow	Up to 1000
Binary search	Must be sorted	Fast	Very fast	~10

Sort algorithm comparison:

Algorithm	Small dataset	Large dataset	Memory	Comparisons (1000 items)
Bubble sort	Acceptable	Very slow	Minimal	~1,000,000
Merge sort	Fast	Fast	More needed	~10,000

Key principle: Algorithm choice depends on:

• Dataset size
• Whether data is already sorted
• Available memory
• Need for simplicity versus efficiency

Worked examples

Example 1: Linear search trace (3 marks)

Question: Show the steps of a linear search looking for the value 45 in this list: [23, 67, 45, 12, 89]. State whether the search is successful.

Mark scheme answer:

1. Check position 0: 23 ≠ 45 — continue [1 mark]
2. Check position 1: 67 ≠ 45 — continue
3. Check position 2: 45 = 45 — found at position 2 [1 mark]
4. The search is successful [1 mark]

Example 2: Binary search explanation (4 marks)

Question: Explain why binary search is more efficient than linear search for finding a student's record in a database of 10,000 students sorted by ID number.

Mark scheme answer:

Binary search eliminates half the remaining data with each comparison [1 mark], whereas linear search checks each record one at a time [1 mark]. For 10,000 records, binary search needs at most 14 comparisons (log₂ 10,000) [1 mark], while linear search could need up to 10,000 comparisons if the target is at the end or not present [1 mark].

Example 3: Bubble sort implementation (6 marks)

Question: Complete one full pass of bubble sort on this list, showing the list state after each swap: [8, 3, 7, 1]. Circle the elements being compared at each step.

Mark scheme answer:

Initial list: [8, 3, 7, 1]

Step 1: Compare 8 and 3 → swap → [3, 8, 7, 1] [1 mark]

Step 2: Compare 8 and 7 → swap → [3, 7, 8, 1] [1 mark]

Step 3: Compare 8 and 1 → swap → [3, 7, 1, 8] [1 mark]

After one complete pass, the largest value (8) is in its correct position [1 mark]. Three comparisons were made [1 mark], and three swaps were needed [1 mark].

Common mistakes and how to avoid them

• Forgetting binary search requires sorted data — Always check the question states the list is sorted before choosing binary search. If unsorted, binary search will not work correctly.

• Losing track during bubble sort passes — Draw each step clearly. Remember that after each complete pass, one more element is in its final position at the end of the list.

• Confusing number of passes with number of comparisons — Bubble sort on n items needs up to n-1 passes, but many more comparisons. Be precise about what the question asks.

• Misunderstanding merge sort's divide phase — Keep dividing until you have individual elements (sublists of size 1), not when you reach two elements. Single elements are considered sorted.

• Using vague efficiency descriptions — Don't write "binary search is faster." Instead, state that "binary search needs log₂(n) comparisons compared to linear search's n comparisons."

• Forgetting to state when a search is unsuccessful — If tracing a search that doesn't find the target, clearly state "not found" or "search unsuccessful" as your conclusion.

Exam technique for "Algorithms: Searching and Sorting"

• Command words matter: "Describe" requires explanation of how an algorithm works (2-3 marks). "State" needs only the fact (1 mark). "Compare" requires discussion of two algorithms with advantages/disadvantages (4-6 marks).

• Show your working for traces: When asked to trace an algorithm, write each step on a new line with the current state of the list. Examiners award marks for partially correct working even if the final answer is wrong.

• Use correct terminology: Write "comparisons" not "checks," "iteration" not "loop," and "adjacent elements" not "next to each other." GCSE mark schemes expect precise subject vocabulary.

• Justify algorithm choice: When asked which algorithm to use, don't just name it — explain why it's suitable for the given scenario (data size, whether sorted, efficiency needs). Two-part answers earn full marks.

Quick revision summary

Linear search checks each element sequentially; binary search halves the search space each time but needs sorted data. Bubble sort repeatedly swaps adjacent elements in wrong order; merge sort divides, sorts, then merges sublists. Binary search and merge sort are much more efficient for large datasets. Linear search works on any list; binary search needs sorted data. Bubble sort is simple but slow; merge sort is faster but uses more memory. Algorithm choice depends on data size, order, and efficiency requirements.