Searching and Sorting Algorithms
This section is examined by asking you to write the algorithms, not merely describe them.
Four are required: linear search, binary search, bubble sort and insertion sort. You must also be able to state
the conditions each one needs, and how its performance changes with the number of data items.
1. Linear Search
A linear search examines each element in turn until the target is found or the data is exhausted.
FUNCTION LinearSearch(Items : ARRAY[1:n] OF INTEGER, Target : INTEGER) RETURNS INTEGER
DECLARE Index : INTEGER
Index ← 1
WHILE Index <= n
IF Items[Index] = Target THEN
RETURN Index // found - return its position
ENDIF
Index ← Index + 1
ENDWHILE
RETURN -1 // -1 signals "not present"
ENDFUNCTION
- The data does not need to be sorted
- Works on any list, including linked lists
- On average it inspects half the items; in the worst case, all of them
2. Binary Search
A binary search repeatedly halves the search area. It compares the target with the middle element and discards the half that cannot contain it.
Two conditions are essential, and both are examined:
- The data must already be sorted.
- The structure must allow direct access to any element by index — so an array works, but a linked list does not.
FUNCTION BinarySearch(Items : ARRAY[1:n] OF INTEGER, Target : INTEGER) RETURNS INTEGER
DECLARE Low, High, Mid : INTEGER
Low ← 1
High ← n
WHILE Low <= High
Mid ← (Low + High) DIV 2
IF Items[Mid] = Target THEN
RETURN Mid
ELSE
IF Items[Mid] < Target THEN
Low ← Mid + 1 // discard the lower half
ELSE
High ← Mid - 1 // discard the upper half
ENDIF
ENDIF
ENDWHILE
RETURN -1
ENDFUNCTION
How performance varies with the number of items
Each comparison halves the remaining data, so the number of comparisons grows very slowly as the data grows.
| Number of items | Maximum comparisons (binary) | Maximum comparisons (linear) |
|---|---|---|
| 10 | 4 | 10 |
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
Doubling the data adds only one extra comparison. This is the point examiners look for: the relationship is logarithmic, not proportional.
Always state that the data must be sorted. Questions asking why a binary search cannot be used
almost always want either "the data is not in order" or "a linked list has no direct access to the middle
element". Answers about speed alone do not score.
3. Bubble Sort
A bubble sort compares adjacent pairs and swaps them if they are out of order, repeating until a complete pass makes no swaps.
PROCEDURE BubbleSort(Items : ARRAY[1:n] OF INTEGER)
DECLARE Temp : INTEGER
DECLARE Swapped : BOOLEAN
DECLARE Top : INTEGER
Top ← n - 1
REPEAT
Swapped ← FALSE
FOR Index ← 1 TO Top
IF Items[Index] > Items[Index + 1] THEN
Temp ← Items[Index] // 3-step swap
Items[Index] ← Items[Index + 1]
Items[Index + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT Index
Top ← Top - 1 // largest is now in place
UNTIL Swapped = FALSE
ENDPROCEDURE
Why the Swapped flag matters. Without it the sort always performs
every pass. With it, an already-sorted list is detected after a single pass. This is exactly what is meant by
"performance depends on the initial order of the data".
4. Insertion Sort
An insertion sort builds a sorted section at the front of the list. Each new item is inserted into its correct place within that sorted section, shifting larger items to the right.
PROCEDURE InsertionSort(Items : ARRAY[1:n] OF INTEGER)
DECLARE Current : INTEGER
DECLARE Pointer : INTEGER
FOR Index ← 2 TO n // item 1 is already "sorted"
Current ← Items[Index]
Pointer ← Index - 1
WHILE Pointer >= 1 AND Items[Pointer] > Current
Items[Pointer + 1] ← Items[Pointer] // shift right
Pointer ← Pointer - 1
ENDWHILE
Items[Pointer + 1] ← Current // drop into the gap
NEXT Index
ENDPROCEDURE
Worked trace
Sorting 7, 3, 9, 4 with an insertion sort:
| Pass | Item taken | Action | List after |
|---|---|---|---|
| 1 | 3 | 7 shifts right, 3 inserted at front | 3, 7, 9, 4 |
| 2 | 9 | Already larger than 7, stays put | 3, 7, 9, 4 |
| 3 | 4 | 9 and 7 shift right, 4 inserted after 3 | 3, 4, 7, 9 |
5. Comparing the Two Sorts
| Bubble sort | Insertion sort | |
|---|---|---|
| Method | Swaps adjacent pairs repeatedly | Inserts each item into a sorted section |
| Best case | Already sorted — one pass with the flag | Already sorted — no shifting needed |
| Worst case | Reverse order | Reverse order — every item shifts the full distance |
| Typical behaviour | Many swaps, simple to code | Fewer comparisons in practice; efficient on nearly-sorted data |
Both sorts share two properties the syllabus asks about explicitly: performance depends on the
initial order of the data and on the number of data items. Neither is efficient
for large data sets.
6. Exam Focus
Learn to write these, not just recognise them. Marks are awarded for the loop structure, the
comparison, and correct handling of the swap or shift. Practise writing all four from memory.
The swap needs a temporary variable. Writing A ← B then
B ← A loses the first value. This remains one of the most common errors at
A Level, not just IGCSE.
Watch the insertion-sort boundary. The loop starts at index 2, and the final
placement is at Pointer + 1, not Pointer. Both are
frequent slips in written answers.
Do not confuse the sorts. Bubble sort compares adjacent items; insertion sort
shifts and inserts. Describing one with the other's mechanism scores nothing even if the name is right.
Quick self-check
- State the two conditions necessary for a binary search.
- A sorted array holds 2 000 items. What is the maximum number of comparisons a binary search needs?
- Write a bubble sort that stops early when the data is already sorted.
- Trace an insertion sort on 5, 2, 8, 1, showing the list after each pass.
- Explain why a binary search cannot be used on a linked list.