Searching and sorting algorithms
Trace and construct linear search, binary search, bubble sort, insertion sort and merge sort, then compare their behaviour.
Section 9 · Algorithm design
Mapped to the Cambridge IGCSE Computer Science 0265 syllabus for exams in 2029. These original explanations and self-checks are independent study support, not Cambridge papers, official marks or grades. Practical programming is taught with worked code and trace tasks; an executable Python workspace and timed digital-exam simulation are not yet available.
Before you begin
- Use the 2029 syllabus for this course. Cambridge specifies Python 3.10 or higher for programming and digital exams for both components. The syllabus currently identifies this route for 2029 only; confirm later-year availability with Cambridge and your school.
Work on paper. Try each question before revealing help, and explain why your method works.
Quick readiness check
Before searching and sorting algorithms, which statement is the safest starting point?
What you will learn
- Show and describe the specified search and sort algorithms
- Construct linear search and bubble sort
- Compare features and efficiency without Big-O notation
Searching depends on the data arrangement
Linear search checks items one by one until the target is found or the list ends. Binary search compares with the middle item and repeatedly discards half the sorted search range. Binary search requires the data to be sorted first.
When tracing, show the current index or remaining range and record each comparison. A search must state what happens if the target is absent; stopping at the end should not accidentally return a match.
Sorting rearranges values by comparisons
Bubble sort repeatedly compares adjacent values and swaps them if they are out of order. Insertion sort grows a sorted region by inserting each next value into its correct position. Merge sort divides data into smaller parts, sorts them and merges the sorted parts.
A clear comparison discusses steps, data conditions and work required. Linear search can stop early but may inspect every item. Binary search reduces the remaining range quickly but needs sorted data. Bubble and insertion are straightforward for small lists; merge sort handles large lists more efficiently but needs extra storage and more complex steps. Big-O notation is not required for this comparison.
Pause and explain
Which habit best checks your understanding of searching and sorting algorithms?
Worked example
Use linear search to find 7 in [4, 7, 2].
Show the worked solution
- Compare 7 with the first item 4: no match.
- Compare 7 with the second item 7: match.
- Stop and return the second position (index 1).
Answer Found at index 1 after two comparisons.
Try a topic test
Choose Easy, Normal or Difficult. Save your answers and open worked review after finishing.
Test this topic →From guided practice to a new situation
Write your answer and reasoning first. Use a hint only if you are stuck. The model solution is for self-checking; your written work is not automatically marked.
Trace binary search for 12 in sorted [2, 5, 8, 12, 16, 20, 25]. Show the midpoint checks.
Give me a hint
Keep the sorted range and choose its middle each time.
Compare my reasoning
- Middle index 3 contains 12.
- The target matches immediately.
- Stop after one comparison.
Found 12 at index 3 after one comparison.
Look for these in your work
- Midpoint chosen
- Match identified
- Stop condition
Perform one full left-to-right bubble-sort pass on [6, 2, 5, 1]. Show the list after each adjacent comparison.
Give me a hint
Compare positions 0–1, then 1–2, then 2–3.
Compare my reasoning
- Compare 6 and 2; swap → [2, 6, 5, 1].
- Compare 6 and 5; swap → [2, 5, 6, 1].
- Compare 6 and 1; swap → [2, 5, 1, 6].
After one pass: [2, 5, 1, 6].
Look for these in your work
- Adjacent comparisons
- Swaps correct
- Pass complete
A library has an unsorted list of 20 book IDs and will search it once, then later search thousands of times. Recommend a search approach for each stage and justify the trade-off.
Give me a hint
Consider whether sorting cost can be reused across many searches.
Compare my reasoning
- For one search, linear search avoids a separate sorting step.
- If many searches will follow, sorting once can make repeated binary searches practical.
- The choice depends on how often the list changes and whether the cost of sorting is worthwhile.
Linear for one immediate search; sort then use binary search if many searches reuse stable data.
Look for these in your work
- One-off cost considered
- Repeated use considered
- Condition stated
Common mistakes
- Using binary search on unsorted data.
- Forgetting zero-based indexing when reporting a position.
- Claiming merge sort uses no extra storage.
What can you explain now?
What condition must be true before binary search is used?
Compare with the explanation
The data must be sorted
Binary search decides which half to discard by comparing order.
After trying it yourself, choose your next review. This is your self-assessment.
Your review choice appears on Today. Sign in to sync it across devices.
Make it stick
How do the preconditions and steps of linear/binary search and the named sorting algorithms differ?
If you needed the solution, close it and solve the problem again from a blank page. A correct answer is stronger when you can explain the reason for each step.