/en-tutor-prep-s6-ict-sorting-searching-algorithms-practice-3/
/en-tutor-prep-s6-ict-sorting-searching-algorithms-practice-3/
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 (challenge)

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)

  1. FoundationBubble sorting 10 items, what is the worst-case total number of comparisons?
  2. FoundationWhy does 10 comparisons suffice for 1000 items in binary search, argued with powers of two?
  3. FoundationMerge sort splits 16 items into 4 levels; if each level costs at most 16 comparisons, what is the upper bound on comparisons?
  4. IntermediateWhy is “at least 2 comparisons” not enough to sort 3 items?
  5. IntermediateBinary searching 1000 sorted items for an absent value, what is the worst case compared with linear search?
  6. IntermediateSelection sorting 10 items, what are the worst-case comparison and swap counts?
  7. ChallengeFor 1000 items, how many times more work is O(n^2) than O(n log n)?
  8. ChallengeSelection sorting [9, 4, 6, 2] ascending, what is the array after the first pass?
  9. ChallengeWhy is linear search’s advantage only about 2 times for a single search, and what changes at 100 searches?
  10. 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.

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