GCSE Computer Science: Sorting and Searching Traces

Standard algorithms are examined by asking students to apply them to a given list and write down the state after each step, so a vague memory of 'it splits the list' is not enough. This material trains exactly that skill, based on the DfE GCSE subject content for computer science, which names standard algorithms including binary search and merge sort, the use of flowcharts and pseudocode, and evaluating how efficiently algorithms meet their requirements without formal comparisons.

The quiz has twelve questions, and every list needed is written in the question. Two questions trace an insertion sort: the list after the third pass, and what is and is not settled half-way through. Three follow a merge sort: how many rounds of merging eight items need, the first items produced when two sorted lists are merged, and the pairs formed in the first round. Two trace a binary search on an eleven-item list with the midpoint rule stated: the items examined when the target is present, and the number examined before a missing item is reported. Three compare efficiency: the most items a binary search examines in a sorted list of a thousand, merge sort against bubble sort for half a million records, and why an insertion sort handles a nearly sorted list well. The last two are flowcharts: choosing the right symbol and tracing a loop described in words. Insertion sort is named on some specifications, for example OCR's; merge sort, bubble sort, linear and binary search appear on the main ones.

The explanations show the full trace, so a wrong answer points to the step that went astray. The flashcards cover how each algorithm works, the requirement for binary search, the merge rounds, the efficiency trade-offs and the four main flowchart symbols.

The written work sets eight longer tasks to answer on paper, each with a model answer and marking points: a full insertion sort, a full merge sort with every round, a binary search trace for a value that is not there, comparing merge and bubble sort, explaining why binary search needs sorted data, designing a flowchart in words to find the largest of ten numbers, explaining insertion sort on nearly sorted data and working out the most examinations for 64 items.

The oral practice with an examiner is a good final check: the examiner gives a short list, asks for the state after each step and gives brief feedback at the end. The material suits Year 10 and Year 11 students preparing for the algorithms and programming paper.

• Apply an insertion sort to a list and state the list after each pass
• Apply a merge sort: split a list into single items and merge sorted lists step by step
• Trace a binary search, stating the items examined, including when the target is missing
• Compare the efficiency of linear and binary search, and of bubble, insertion and merge sort
• Name flowchart symbols and trace an algorithm given as a flowchart

Practice material written by Zestly, based on the DfE GCSE subject content for computer science (standard algorithms including binary search and merge sort; pseudocode and flowcharts; evaluating efficiency) and the algorithms sections of the AQA (8525, 3.1) and OCR (J277, 2.1) GCSE Computer Science specifications.