S6 ICT: Sorting and Searching (intermediate)
- 2026-11-20
S6 ICT: Sorting and Searching (intermediate)
The second paper traces passes and scales the numbers up: what the array looks like after each pass and how many comparisons a thousand or a million items need.
Intermediate: pass-by-pass traces and scaling Bubble sort turns [4, 2, 7, 1] into [2, 4, 1, 7] after one pass; binary search needs 10 comparisons for 1000 items (2^10 = 1024) and only 20 for 1,000,000. Insertion sort makes 15 comparisons on 6 reversed items and merge sort builds 3 levels for 8. Linear search costs 100 times more than binary at 1000, while selection and bubble sort both take 499500.
01 Paper details (check answers afterwards)
| Item | Detail |
|---|---|
| Questions | 10 |
| Suggested time | 25 |
| Difficulty mix | Foundation 3 · Intermediate 3 · Challenge 3 · Error redo 1 |
| Chapter | Chapter: S6 ICT: Sorting and Searching Algorithms |
| Level | Intermediate (10 items) |
02 Questions (10 items)
- FoundationBubble sorting [4, 2, 7, 1] ascending, what is the array after pass one?
- FoundationBinary searching 1000 sorted items, what is the maximum number of comparisons?
- FoundationBinary searching 1,000,000 sorted items, what is the maximum number of comparisons?
- IntermediateHow many comparisons does insertion sort make on 6 items in reverse order (worst case)?
- IntermediateHow many levels does merge sort create for 8 items?
- IntermediateFor 1000 items, how many times more comparisons does linear search need than binary search in the worst case?
- ChallengeFor 1000 items, how do selection and bubble sort compare in worst-case comparison count?
- ChallengeIn sorted [2, 5, 8, 11, 14, 17], binary search looks for 11; which element is compared second?
- ChallengeEven with sorted data, why is linear search still reasonable to find the first item meeting a condition among 1 000?
- Error redoError: the midpoint is written as (low + high) / 2. What is wrong?
03 Answers and one-line notes
| # | Answer | One-line note |
|---|---|---|
| 1 | [2, 4, 1, 7]: 4 swaps with 2, 7 stays, then 7 swaps with 1. | Pass one only fixes the maximum 7 at the end; the first three are still unsorted. |
| 2 | 10, because 2^10 = 1024 which is at least 1000. | Once a power of two covers 1000, the range narrows to a single element. |
| 3 | 20, since 2^20 = 1,048,576. | Each extra comparison doubles the reachable size, so a million items need only twenty. |
| 4 | 15, that is 6 x 5 / 2. | In reverse order each new item is compared all the way to the front, totalling 1+2+3+4+5 = 15. |
| 5 | 3, since halving repeatedly gives 2^3 = 8. | 8 halves to 4, 2, 1 in 3 splits, which is why merge sort is O(n log n). |
| 6 | 1000 versus 10, that is 100 times more. | 1000/10 = 100, and the gap widens as data grows. |
| 7 | Identical at 499500 = 1000 x 999 / 2. | Both compare pairs to establish order; they differ in swaps, where selection sort needs at most n-1. |
| 8 | First 8 (the lower midpoint) narrows the range to [11, 14, 17], the second comparison is 11, a hit. | The midpoint of six elements is 8 at index 2; since 11 is larger, the right half is searched. |
| 9 | Scanning from the front stops at the first match, which is the simplest correct route when the target is a first occurrence. | Binary search suits equality; for the earliest item satisfying a predicate, a forward scan is easier to get right. |
| 10 | An integer index needs floor division: (low + high) // 2. | True division yields a fractional index, which either raises an error or truncates unpredictably. |
04 What to do after marking
- After marking, redo only the wrong items and write down which step went wrong (formula, unit, or misread number).
- Repeat the same item two days later; move to the next paper only when both attempts are correct.
- Parents only need the answer and note columns; there is no need to explain every item.
Want to separate bubble, selection, insertion and merge sort, then replace a linear scan with binary search? Book a TutorZone tutor and count every comparison in twenty-five minutes.Tutor Registration →
Questions and answers are written originally by the TutorZone team and are not taken from any school, publisher or examination authority paper. Every value is checked by computer.



