S6 ICT: Sorting and Searching (challenge)
- 2026-11-20
S6 ICT: Sorting and Searching (challenge)
The third paper works on complexity and the information-theoretic lower bound: why 3 items need 3 comparisons and how far n^2 sits from n log n.
Challenge: complexity and comparison bounds Bubble sort takes 45 comparisons on 10 items; merge sort on 16 builds 4 levels bounded by 64; at 1000 items O(n^2) costs about 499500 against 10000 for O(n log n), roughly 50 times. Three items have 6 permutations while 2 comparisons separate only 4, so 3 comparisons are required (2^3 = 8). Selection sort takes 45 comparisons on 10 items but only 9 swaps.
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 | Challenge (10 items) |
02 Questions (10 items)
- FoundationBubble sorting 10 items, what is the worst-case total number of comparisons?
- FoundationWhy does 10 comparisons suffice for 1000 items in binary search, argued with powers of two?
- FoundationMerge sort splits 16 items into 4 levels; if each level costs at most 16 comparisons, what is the upper bound on comparisons?
- IntermediateWhy is “at least 2 comparisons” not enough to sort 3 items?
- IntermediateBinary searching 1000 sorted items for an absent value, what is the worst case compared with linear search?
- IntermediateSelection sorting 10 items, what are the worst-case comparison and swap counts?
- ChallengeFor 1000 items, how many times more work is O(n^2) than O(n log n)?
- ChallengeSelection sorting [9, 4, 6, 2] ascending, what is the array after the first pass?
- ChallengeWhy is linear search’s advantage only about 2 times for a single search, and what changes at 100 searches?
- Error redoError: assuming an item keeps the same index after sorting. Why is that wrong?
03 Answers and one-line notes
| # | Answer | One-line note |
|---|---|---|
| 1 | 45 = 10 x 9 / 2. | Each pass shortens by one: 9+8+…+1 = 45, matching n(n-1)/2. |
| 2 | Because 2^10 = 1024 which covers 1000, so 10 halvings reduce the range to one item. | Each comparison halves the candidates, so k comparisons cover at most 2^k items. |
| 3 | 64, that is 16 x 4. | 4 levels x 16 = 64, exactly the n log n scale. |
| 4 | Three items have 6 permutations but 2 comparisons only distinguish 4 outcomes, so information is insufficient. | Each comparison is binary, so k comparisons separate at most 2^k cases and 3 are needed (2^3 = 8 >= 6). |
| 5 | Binary still needs at most 10 while linear needs 1000, a factor of 100. | A miss still halves each time and stops when low exceeds high, so the count is unchanged. |
| 6 | 45 comparisons and at most 9 swaps. | Comparisons are always n(n-1)/2 = 45 while swaps settle one item per pass, so 9. |
| 7 | About 499500 versus 10000, roughly 50 times more. | 499500 / 10000 is about 50, and the gap keeps growing with size. |
| 8 | [2, 4, 6, 9]: the minimum 2 swaps with the leading 9. | Selection sort places the minimum into the next slot, so the first element is settled after one pass. |
| 9 | For 8 items 8 versus 3 is only 2 times, but sorting once then searching 100 times beats 100 full scans. | Sorting costs about 20 comparisons here, so whether it pays depends on n and on how many searches follow. |
| 10 | Sorting moves items, so indexes change; keep the original identifier in a separate field. | A common slip is matching the sorted index to the original record and pairing the wrong entries. |
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.



