/en-tutor-prep-s6-ict-sorting-searching-algorithms-practice-2/
/en-tutor-prep-s6-ict-sorting-searching-algorithms-practice-2/
General Inquiry: info@TutorZone.com.hk
Office Hours: Monday to Saturday - 9:00 AM to 6:00 PM
WhatsApp Monday to Sunday - 24 hours
Hotline: +852 6828 1809
Instant Support: +852 9061 3106

S6 ICT: Sorting and Searching (intermediate)

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)

  1. FoundationBubble sorting [4, 2, 7, 1] ascending, what is the array after pass one?
  2. FoundationBinary searching 1000 sorted items, what is the maximum number of comparisons?
  3. FoundationBinary searching 1,000,000 sorted items, what is the maximum number of comparisons?
  4. IntermediateHow many comparisons does insertion sort make on 6 items in reverse order (worst case)?
  5. IntermediateHow many levels does merge sort create for 8 items?
  6. IntermediateFor 1000 items, how many times more comparisons does linear search need than binary search in the worst case?
  7. ChallengeFor 1000 items, how do selection and bubble sort compare in worst-case comparison count?
  8. ChallengeIn sorted [2, 5, 8, 11, 14, 17], binary search looks for 11; which element is compared second?
  9. ChallengeEven with sorted data, why is linear search still reasonable to find the first item meeting a condition among 1 000?
  10. 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.

Join as a tutor or coach — academic, music, sports, arts, STEM. Free to register. See how it works →