aiMOOC

Comparing search and sorting algorithms - Computing Year 9

QR-Code

Introduction

Trace the required binary search and merge-sort examples,run an original comparison module and judge algorithm suitability from explicit evidence. State preconditions,duplicate behaviour,counter definitions and preparation costs. Year9 is editorial KS3 progression with a bridge to England’s current GCSE Computer Science content.

Compare search contracts and trace binary search

Ask the same question before comparing methods

Searching asks whether an item is present and may return a position. Sorting rearranges items into an order. These are different tasks, so a small count from one is not evidence that it replaces the other. A reasoned comparison states the input, required output, preconditions and what is being counted. It also considers the cost of preparing data and whether the task happens once or repeatedly.

For this course, search inputs are integer lists and the result is a zero-based index or None. Linear search returns the first matching position in the supplied list. The binary search stops at its first matching midpoint, which need not be the leftmost duplicate. Both answers can be correct for a membership task, while only one satisfies a requirement for the first occurrence. Index zero is a valid success; do not treat every false-like result as failure.

Binary search relies on ascending order so it can safely discard one side of an interval. Our implementation checks that precondition and rejects an unsorted list. Silently running the halving rule on arbitrary data can miss a present item. Sorting first changes positions and has its own cost. If an original record position matters, preserve a mapping rather than pretending a sorted index still names the original row.

Trace the exact midpoint convention

The required sorted list is [2,5,8,11,14,17,20]. Search for14 using inclusive low/high bounds and the lower middle when an interval has even length. Start at low0,high6,mid3,value11. Since14 is greater, discard positions0 through3. With low4,high6,mid5,value17, discard positions5 through6. With low4,high4,mid4,value14, return index4. The visited values are11,17,14: three probes, not two and not the target value as an index.

Probe	Low	High	Midpoint	Value	Next action
1	0	6	3	11	Search positions4 to6
2	4	6	5	17	Search position4 only
3	4	4	4	14	Return index4

Searching for13 visits11,17,14 and then has no candidate positions; it returns None. A loop must shrink the interval or stop after a match. Reusing the same midpoint without moving past it can cause a non-terminating search. An empty list starts with high−1 and low0, so no probe is performed.

CS50: Binary Search. Pause at each discarded interval and compare the assumptions and midpoint convention with the complete original trace here.

For [2,2,2], this binary search returns index1 in one probe, while linear search returns index0 in one probe. Neither has discovered a different stored value. Their output contracts differ for duplicates. Write the requirement before deciding whether this difference is a bug or an acceptable result.

Build merge sort from ordered parts

Divide, sort the parts, then merge

Merge sort divides a list into smaller parts, sorts those parts and merges ordered results. Merging is not simply joining arbitrary lists, and it is not repeatedly swapping neighbouring values. The merge operation repeatedly compares the first remaining key from each already-sorted part, takes the smaller and eventually appends the unconsumed tail. A tail needs no further comparison between the two runs once the other run is empty.

For [8,3,6,2], split into [8,3] and [6,2], then into single-item parts. Merge [8] with [3] to produce [3,8] using one key comparison. Merge [6] with [2] to produce [2,6] using one. Finally merge [3,8] and [2,6]: compare3 with2,take2;compare3 with6,take3;compare8 with6,take6;append8. This final merge uses three comparisons, making five across the full sort.

Merge event	Ordered inputs	Output	Key comparisons
First left merge	[8] and [3]	[3,8]	1
First right merge	[6] and [2]	[2,6]	1
Final merge	[3,8] and [2,6]	[2,3,6,8]	3
Total	Original[8,3,6,2]	[2,3,6,8]	5

The other required task begins with [7,1] and [6,3]. These are unsorted pairs, so sort each first: [1,7] and [3,6]. The final merge produces [1,3,6,7] with three comparisons; sorting the two pairs adds two more. A public merge-only function should reject the original unsorted pairs rather than silently imply that its ordered-input precondition is satisfied.

Complete original executable comparison

Run this full Python3 module in a school-approved practice environment. It includes checked search functions, a checked two-run merge, merge sort and a shrinking-pass bubble sort with early stopping. Lists contain at most64 whole integers from−100 to100; Boolean values are rejected. A search target must be an integer and may be outside the stored range. Inputs are preserved; returned values and traces are new objects.

def checked_values(values):
    if type(values) is not list or len(values) > 64:
        raise ValueError("use a list with at most 64 integers")
    if any(type(v) is not int or not (v >= -100 and 100 >= v) for v in values):
        raise ValueError("use whole integers from -100 to 100")


def linear_search(values, target):
    checked_values(values)
    if type(target) is not int:
        raise ValueError("target must be an integer")
    trace = []
    for index, value in enumerate(values):
        trace.append({"index": index, "value": value})
        if value == target:
            return {"index": index, "probes": len(trace), "trace": trace}
    return {"index": None, "probes": len(trace), "trace": trace}


def binary_search(values, target):
    checked_values(values)
    if type(target) is not int:
        raise ValueError("target must be an integer")
    if any(values[i-1] > values[i] for i in range(1, len(values))):
        raise ValueError("binary search requires ascending order")
    low, high = 0, len(values) - 1
    trace = []
    while high >= low:
        mid = (low + high) // 2  # Lower middle for an even interval.
        value = values[mid]
        trace.append({"low": low, "high": high, "mid": mid, "value": value})
        if value == target:
            return {"index": mid, "probes": len(trace), "trace": trace}
        if value > target:
            high = mid - 1
        else:
            low = mid + 1
    return {"index": None, "probes": len(trace), "trace": trace}


def merge_sorted_parts(left, right):
    # Internal helper: callers supply already sorted parts.
    out = []
    i = j = comparisons = 0
    while len(left) > i and len(right) > j:
        comparisons += 1
        if right[j] >= left[i]:  # Choose the left on equal keys.
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:]); out.extend(right[j:])
    return out, comparisons


def merge_runs(left, right):
    checked_values(left); checked_values(right)
    if len(left) + len(right) > 64:
        raise ValueError("combined length must be at most 64")
    for part in [left, right]:
        if any(part[i-1] > part[i] for i in range(1, len(part))):
            raise ValueError("each merge input must already be sorted")
    out, comparisons = merge_sorted_parts(left, right)
    return {"values": out, "comparisons": comparisons}


def merge_sort(values):
    checked_values(values)
    events = []
    def sort_part(part):
        if 1 >= len(part):
            return part.copy(), 0
        mid = len(part) // 2
        left, left_cost = sort_part(part[:mid])
        right, right_cost = sort_part(part[mid:])
        out, cost = merge_sorted_parts(left, right)
        events.append({"left": left, "right": right,
                       "output": out, "comparisons": cost})
        return out, left_cost + right_cost + cost
    out, total = sort_part(values)
    return {"values": out, "comparisons": total, "merges": events}


def bubble_sort(values):
    checked_values(values)
    work = values.copy()
    comparisons = swaps = 0
    passes = []
    for end in range(len(work)-1, 0, -1):
        changed = False
        for i in range(end):
            comparisons += 1
            if work[i] > work[i+1]:
                work[i], work[i+1] = work[i+1], work[i]
                swaps += 1; changed = True
        passes.append(work.copy())
        if not changed:
            break
    return {"values": work, "comparisons": comparisons,
            "swaps": swaps, "passes": passes}


if __name__ == "__main__":
    values = [2, 5, 8, 11, 14, 17, 20]
    found = binary_search(values, 14)
    print("binary", found["index"], found["probes"],
          [row["value"] for row in found["trace"]])
    for sample in [[8, 3, 6, 2], [1, 2, 3, 4], [4, 3, 2, 1]]:
        m = merge_sort(sample); z = bubble_sort(sample)
        print(sample, m["values"], "merge", m["comparisons"],
              "bubble", z["comparisons"])

The private merge helper assumes its callers supply sorted parts. merge_runs checks that public precondition; merge_sort establishes it recursively through single-element base cases. Each recursive split is smaller until length zero or one, so it reaches a base case. The postorder merge events show completed merges, not a claim that every event is at the same recursion depth.

Equal keys are taken from the left part before the right part. This tie rule supports stable merging when records have equal sorting keys; this teaching program accepts integers and does not itself attach record identities. Duplicate values must be preserved. An empty list is already ordered and returns an empty result with zero comparisons. Do not convert duplicate-containing data into a set just to make sorting easier.

CS50 Shorts: Merge Sort. Pause during the merge and predict which sorted part supplies the next value; distinguish dividing a list from ordering the returned parts. Original: CS50, Merge Sort - CS50 Shorts. The written explanations and native tasks work without sound or the external player.

Our merge implementation creates slices and new lists. It is not an in-place sorter and does not promise a memory or timing benchmark. The bubble implementation works on a copy, compares adjacent keys, shrinks the unsorted end and stops after a pass with no swaps. Counts apply to these stated implementations, not every possible variant.

Evaluate algorithms with fair, bounded evidence

Count a declared operation, not an impression

A search probe here means inspecting one candidate value. It is not a count of every Python comparison, validation check, memory access or processor instruction. A sorting comparison here means comparing keys from the data. Loop conditions, input checks, slicing and copying are excluded from that counter. Compare searches with the same probe convention and sorts with the same key-comparison convention; do not treat all counters as identical units of complete work.

Target in the seven-item sorted list	Linear probes	Binary probes	Reason
2	1	3	Linear finds the first item immediately
11	4	1	Binary’s initial midpoint matches
14	5	3	Required trace11,17,14
13 absent	7	3	Binary exhausts the remaining interval
21 absent	7	3	Binary checks11,17,20 then stops

Binary search is not always fewer probes for a particular small input and target. The first row provides a counterexample. Conversely, repeated searches over a large already-ordered structure may benefit from discarding large candidate intervals. The right recommendation depends on order, size, frequency of queries, required duplicate behaviour and preparation cost. Test evidence supports a bounded claim; one favourable row is not a universal proof.

This public binary wrapper checks the entire list's order on every call, so the whole checked function does not have the halving core's logarithmic total cost. The reported probe counter excludes that scan. A real design might establish and maintain sortedness separately, but must then define how updates preserve it. Never remove a check silently just to publish an attractive speed claim. Sorting an unordered list for a single query may cost more than a straightforward linear search.

Four-item input	Merge-sort comparisons	Bubble comparisons	What it shows
[1,2,3,4]	4	3	Bubble’s no-swap stop helps an already sorted small list
[4,3,2,1]	4	6	Input order changes the comparison result
[8,3,6,2]	5	6	Both return[2,3,6,8]with different processes

These are operation counts from the original implementations, not measured seconds. A runtime measurement also depends on environment, implementation overhead, input generation and repetition. Do not label a six-versus-five comparison result as a particular percentage faster in real use. Correctness comes before efficiency: a method that omits values or violates a precondition has not solved the same problem more cheaply.

Design evidence that can challenge your recommendation

Include an empty list,a single item,already ordered and reverse-ordered data,duplicates,a target at the beginning,a target near the end and an absent target. Predict the output before execution. Check sorted results against an independent reference and ensure the same multiset of values remains. Verify the input was not modified when preservation is part of the contract.

For each recommendation, identify at least one trade-off and one case that could change the choice. A single lookup on an unordered collection may suit linear search. Many lookups on maintained sorted data may suit binary search's core. A larger arbitrary-order sorting task may suit a divide-and-merge approach,while a small nearly sorted classroom list illustrates early-stopping bubble behaviour. The course does not require a formal efficiency proof or claim that a GCSE assessment board uses this precise Python interface.

Submit the required binary trace and pair-sorting/final-merge trace,actual output from the full module,a clearly labelled comparison table and a reasoned selection for a new scenario. State assumptions,counter definitions,validation overhead and remaining limits. This Year9 course develops comparison and divide-and-merge reasoning; earlier foundation courses remain separate,with their own stated examples and contracts.

Interactive Tasks

Quiz: Test Your Knowledge

What must this binary search verify before halving intervals? (The supplied integer list is in ascending order) (!The target is guaranteed to be present) (!Every value is unique) (!The list was generated on the same computer)

What values are probed when searching for14 in the required seven-item list? (11,17,14) (!11,14) (!2,5,8) (!14,17,20)

What does the required successful search return as its index? (4) (!14) (!3 because there were three probes) (!5 because linear search made five probes)

What must happen before merging the original pairs [7,1] and [6,3]? (Sort the pairs to [1,7] and [3,6]) (!Delete the larger value from each pair) (!Assume concatenation gives sorted order) (!Remove every duplicate from the entire input)

How many key comparisons does the final merge of [3,8] and [2,6] use? (3) (!1) (!2) (!8)

How many comparisons does the full merge sort of [8,3,6,2] use? (5) (!3 because only the final merge counts) (!4 because there are four items) (!6 because every sort must use six)

For [2,2,2],why may binary and linear search return different indices? (Binary stops at its first matching midpoint while linear returns the first position) (!One of the lists has secretly lost a value) (!A present target must always return None) (!An index can never be zero)

What does the search-probe counter exclude here? (The wrapper’s complete type and sortedness validation) (!Every candidate value inspection) (!The matching midpoint inspection) (!Every absent-target search)

Which result disproves the claim that binary always uses fewer probes? (Searching for the first value2 takes linear1 and binary3 probes) (!Searching for11 takes binary1 probe) (!Searching for14 returns index4) (!The sorted list contains seven values)

What does a five-versus-six comparison count justify? (A bounded difference in the declared key operations for those inputs and implementations) (!A measured percentage improvement in real elapsed time) (!Proof that the smaller-count program is correct on every input) (!Permission to omit input validation without changing the contract)

Memory Game

Precondition	An input requirement needed before an algorithm runs correctly
Probe	One inspected candidate value in this search counter
Merge	Combine already ordered parts into an ordered result
Base case	A small case that stops recursive splitting
Counterexample	A case that contradicts a claimed universal rule
Trade-off	A choice with benefits and costs under stated conditions

Drag and Drop

An arbitrary-order list needs one membership lookup	Consider linear search without first paying to sort
The task requires the first duplicate position	Check the output contract rather than accepting any matching midpoint
Two supplied merge runs are unordered	Sort them first or reject the merge-only call
A probe count ignores an order-validation scan	Report the excluded cost before describing whole-function efficiency
A shorter output is claimed to be a faster sort	Verify value preservation and correctness before comparing work

Crossword Puzzle

BINARY	Which search discards one side of an ordered interval?
LINEAR	Which search visits candidates in supplied order?
MERGE	Which operation combines sorted runs?
RECURSION	What technique solves smaller instances of the same task?
PROBE	What is one inspected search candidate called here?
CONTRACT	What specifies required inputs and outputs?

LearningApps

Optional extra practice. Choose an appropriate activity with your teacher. If the external collection is unavailable, use the native activities and independent tasks in this course.

Cloze Text

Open Tasks

Easy

Separate the problems: Distinguish searching for an item from ordering a list.
Trace the required search: Show low,high,midpoint and value for target14 in the seven-item list.
Merge sorted runs: Merge[1,7]and[3,6],recording comparisons and the unconsumed tail.
Explain index zero: Show why index0 is a success and None represents absence in these functions.

Standard

Complete the required merge-sort task: Sort the pairs[7,1]and[6,3]before their final merge;count both stages.
Run the original module: Record exact search and sort outputs,including input preservation.
Compare fair counters: Build a probe table for present/absent targets and state excluded validation costs.
Select for a scenario: Choose an approach for one unordered lookup and for repeated queries on maintained sorted data,with trade-offs.

Advanced

Challenge a speed claim: Explain why three probes do not establish the total cost of a wrapper that scans order each time.
Handle duplicates deliberately: Specify any-match versus first-occurrence contracts and design appropriate tests.
Design a robust comparison: Include normal,empty,singleton,sorted,reverse,duplicate and absent-target cases with an independent correctness reference.
Evaluate sorting choices: Use the original four-item comparison table,preparation,memory and output requirements to make a bounded recommendation.

Learning Check

Required binary trace: Search for14 in[2,5,8,11,14,17,20]using the declared convention.
Required pair and merge trace: Work from[7,1]and[6,3]to the full sorted result.
Compare target positions: Contrast targets2 and11 for the seven-item list.
Counter scope: Explain why the checked binary wrapper is not logarithmic in total work.
Sort comparison: Give original merge and bubble key counts for sorted and reverse four-item lists.
Correctness boundaries: State expected empty and duplicate behaviour and a useful independent check.

Worked checks and assessment guidance

Bounds0..6 give mid3/value11;bounds4..6 give mid5/value17;bounds4..4 give mid4/value14. Return index4 after three probes. Original index values and probe count are different quantities.
Sort the pairs to[1,7]and[3,6],one comparison each. Final merge compares1/3,takes1;7/3,takes3;7/6,takes6;then appends7. Final merge costs3 and full sorting costs5,output[1,3,6,7].
Target2:linear1 probe,binary3. Target11:linear4,binary1. A method can have fewer probes for one target and more for another;do not claim binary always wins.
It checks every stored value and every adjacent ordering relation before the halving loop. The probe count excludes those scans. Core halving behaviour does not remove validation/preparation costs from the complete function.
Sorted[1,2,3,4]:merge4,bubble3 with no-swap stopping. Reverse[4,3,2,1]:merge4,bubble6. These are declared key-comparison counts,not measured seconds or an efficiency proof for every variant.
Empty search returns None with0 probes;empty sort returns[]with0 comparisons. Duplicates are preserved;on[2,2,2],linear returns0 and binary1 under their contracts. Compare sorted outputs with an independent reference and multiset,then check original input preservation.

Learning evidence

Keep both required traces,exact code/version,actual execution results,counter definitions,correctness/boundary tests and a reasoned recommendation with a counterexample or limitation. Separate search probes,sorting key comparisons and complete runtime/preparation costs. Do not invent a timing benchmark or board-specific assessment approval.

OER and Wikipedia

DfE: England Computing programme,KS3 and DfE: GCSE Computer Science content,updated31March2025;curriculum context,with editorial Year9 allocation and board detail kept separate. Harvard CS50x: Algorithms notes and original Merge Sort short;conceptual and original publisher media references,not copied course code or examples. Reviewed14November2026. All teaching traces,Python source,comparisons and activities here are original.

Python Code.jpg, Weal2019, CC0. Unchanged original; caption and learning activities are original.

CS50: Binary Search - CS50 Shorts;original publisher video,not a partnership claim or relicensing of Harvard’s wider course.