MskProdComputing
All GCSE 6 45 min read 10 question quiz 18 exam marks

Searching and Sorting Algorithms

Linear and binary search, bubble, insertion and merge sort: each one written in Python, traced by hand, and run on real data with a counter so you can see why one beats another.

A search looks for one value in a list and reports where it is, or that it is missing.

Linear search

Check each item in turn, starting at the front, until you find it or run out.

Python
def linear_search(items, target):
    comparisons = 0
    for i in range(len(items)):
        comparisons += 1
        if items[i] == target:
            return i, comparisons
    return -1, comparisons

data = [3, 8, 12, 17, 21, 25, 30, 36, 41, 47, 52, 58, 63, 70, 76]
print(linear_search(data, 63))      # (12, 13): found at position 12 after 13 comparisons
print(linear_search(data, 50))      # (-1, 15): not there, so all 15 items were checked

Linear search works on any list, sorted or not. In the worst case it checks every item.

Binary search

Binary search needs the list to be sorted. It looks at the middle item, and that one comparison throws away half of the list: if the target is bigger, everything at or before the middle is ruled out, and if it is smaller, everything at or after it is.

Binary search narrowing the listA binary search for 63 in a sorted list of fifteen numbers, from 3 up to 76. The first comparison is with position 7, which holds 36. 36 is less than 63, so positions 0 to 7 are ruled out and low becomes 8. The second comparison is with position 11, which holds 58. That is still less than 63, so positions 8 to 11 are ruled out and low becomes 12. The third is with position 13, which holds 70. That is more than 63, so positions 13 and 14 are ruled out and high becomes 12. The fourth is with position 12, which holds 63, so the search ends after four comparisons. A linear search of the same list would have needed thirteen.Binary search for 63 in a sorted list of 15 items308112217321425530636741847952105811631270137614position#lowhighmiditems[mid]decisiontarget = 63381217212530361101473636 < 63, so low = 8381217212530364147525812101473636 < 63, so low = 82814115858 < 63, so low = 1238121721253036414752587076123101473636 < 63, so low = 82814115858 < 63, so low = 1231214137070 > 63, so high = 12381217212530364147525870761234101473636 < 63, so low = 82814115858 < 63, so low = 1231214137070 > 63, so high = 12412121263found it
Every comparison halves what is left, so doubling the list adds only one more comparison.
Python
def binary_search(items, target):
    low = 0
    high = len(items) - 1
    comparisons = 0
    while low <= high:
        mid = (low + high) // 2
        comparisons += 1
        if items[mid] == target:
            return mid, comparisons
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1, comparisons

data = [3, 8, 12, 17, 21, 25, 30, 36, 41, 47, 52, 58, 63, 70, 76]
print(binary_search(data, 63))      # (12, 4)
print(binary_search(data, 50))      # (-1, 4)

Looking for 63, the middle positions checked are 7, 11, 13 and then 12. That is four comparisons where the linear search needed thirteen.

A trace table for binary search

A trace table follows each variable through the algorithm. This is the one the exam asks for, for target = 63:

Passlowhighmiditems[mid]Decision
101473636 < 63, so low = 8
2814115858 < 63, so low = 12
31214137070 > 63, so high = 12
412121263Found at position 12
Binary search on an unsorted list gives wrong answers

It does not crash and it does not warn you. It simply discards the half of the list the item happened to be in. Always say "the list must be sorted" when an exam asks for the condition.

How much faster?

Every comparison halves what is left, so doubling the size of the list adds only one more comparison.

Python
for n in [16, 256, 4096, 65536, 1048576]:
    steps = 0
    size = n
    while size > 0:
        size = size // 2
        steps += 1
    print(n, "items need at most", steps, "comparisons")

A million items in at most 21 comparisons. A linear search of the same list could need a million.

Linear search and binary search, looking for 38Two ways of finding the number 38 in a sorted list of fifteen numbers. In a linear search the program looks at the items one at a time from the left, so it has to look at the first nine and reject each one before it finds 38 on the tenth look. In a binary search the program checks the middle item, which is 30. 38 is bigger, so the whole left half is thrown away. It then checks the middle of what is left, which is 47. 38 is smaller, so the right half is thrown away, leaving three items. The middle of those is 38, found on the third look. Binary search takes 3 looks where linear search took 10, and the gap grows as the list grows, but binary search only works if the list is sorted.Linear search: look at every item in turn381114172126303338424751566012345678910not it, not it, not it ...found it on the 10th look1Binary search: halve the sorted list every time3811141721263033384247515660check the middle: 30. 38 is bigger, so drop the left half3811141721263033384247515660check the middle: 47. 38 is smaller, so drop the right half3811141721263033384247515660check the middle: 38. Found it, on the 3rd look2linear: 10 looksbinary: 3 looksbinary search needs a sorted list3
  1. Linear search looks at every item in turn from the start, so it can be slow.
  2. Binary search checks the middle and throws half the list away each time.
  3. 3 looks against 10. The longer the list, the bigger the gap, but binary search needs the list sorted.
Linear works on any list. Binary is far faster, but only on a sorted one.

Bubble sort and insertion sort

Sorting puts a list in order. The exam names three algorithms, and you must be able to describe each, trace it by hand and complete code for it.

Bubble sort

Compare each pair of neighbours and swap them if they are the wrong way round. After one pass the largest item has been carried to the end, like a bubble rising. Keep making passes until a whole pass has no swaps.

Python
def bubble_sort(items):
    items = items[:]
    n = len(items)
    passes = 0
    swapped = True
    while swapped:
        swapped = False
        for i in range(n - 1 - passes):
            if items[i] > items[i + 1]:
                temp = items[i]
                items[i] = items[i + 1]
                items[i + 1] = temp
                swapped = True
        passes += 1
        print("after pass", passes, items)
    return items

print(bubble_sort([5, 1, 4, 2, 8]))

Run it and watch. After pass 1 the 8 is in place, after pass 2 the 5 is, and pass 3 makes no swaps, so the loop stops.

Two details earn marks:

  • The swap needs a temporary variable. items[i] = items[i + 1] followed by items[i + 1] = items[i] loses a value. Python can swap in one line, items[i], items[i + 1] = items[i + 1], items[i], but the exam swap uses temp.
  • The swapped flag lets the algorithm stop early. Without it, bubble sort always makes the full number of passes, even on a list that was sorted from the start. The n - 1 - passes shortens each pass because the end of the list is already final.

Insertion sort

Take the items one at a time and insert each into its correct place among the ones before it, which are already in order, shifting larger items one place right to make room. It is how most people sort a hand of cards.

Python
def insertion_sort(items):
    items = items[:]
    for i in range(1, len(items)):
        current = items[i]
        j = i - 1
        while j >= 0 and items[j] > current:
            items[j + 1] = items[j]
            j = j - 1
        items[j + 1] = current
        print("inserted", current, "->", items)
    return items

print(insertion_sort([5, 1, 4, 2, 8]))

Notice the 8 does no shifting at all. Insertion sort is quick on a list that is already nearly in order, which bubble sort is not.

Bubble sort on 5, 2, 4, 1, 3Bubble sort drawn with numbered cards. On the left is the first pass, step by step. The two cards being compared are lit up. 5 is bigger than 2, so they swap. 5 is bigger than 4, so they swap again. 5 is bigger than 1 and then 3, and swaps each time, so the 5 has bubbled all the way to the end, where it is in its final place and is shown in green. On the right is the list after every pass: after pass 1 the 5 is in place, after pass 2 the 4 and 5, and after pass 3 the whole list is in order. Pass 4 makes no swaps at all, which is how the algorithm knows it can stop.One pass, step by step524135 > 2: swap254135 > 4: swap245135 > 1: swap241535 > 3: swap241355 is in place123After every passstart52413pass 124135pass 221345pass 312345pass 412345pass 4 made no swaps,so the list is sortedstop when a pass makes no swaps4
  1. Compare two neighbours, and if they are the wrong way round, swap them.
  2. Work along the list. A big value is carried all the way to the end.
  3. After a pass the last item is in its final place, so the next pass can be shorter.
  4. Repeat until a whole pass makes no swaps.
Each pass puts one more item in place. A pass with no swaps means the list is sorted.
Insertion sort on 4, 3, 5, 1, 2Insertion sort drawn as sorting playing cards in your hand. The sorted cards, in green, sit on the left and the unsorted cards, in grey, on the right, with the card currently being placed lifted up in yellow. Start with just the 4 as the sorted part. Take 3: it is smaller than 4, so the 4 shifts right and the 3 goes in front. Take 5: it is bigger than 4, so it stays where it is. Take 1: it is smaller than 3, 4 and 5, so all three shift right and the 1 goes at the front. Take 2: the 3, 4 and 5 shift right and the 2 drops in after the 1. No cards are left, so the list is sorted.like sorting playing cards in your hand43512take 3: it is smaller than 4, so 4 shifts right34512take 5: bigger than 4, so it stays where it is34512take 1: shift 3, 4 and 5 right, then drop it in front13452take 2: shift 3, 4 and 5 right, drop it after 112345no cards left: the list is sorted1234
  1. The sorted part grows from the left, one card at a time.
  2. Take the next card and slide it back past every larger card.
  3. Larger cards shift one place right to make room.
  4. When no cards are left, the whole list is sorted.
Insertion sort is quick on lists that are nearly sorted already, and simple to write.

Merge sort

Merge sort uses divide and conquer. A list of one item is already sorted. So split the list in half again and again until every piece has a single item, then merge the pieces back together in order. Merging two sorted lists is easy: look at the front of each, and take the smaller.

Merge sort: divide, then mergeMerge sort on the list 38, 27, 43, 3, 9, 82, 10. The divide half splits the list into 38, 27, 43, 3 and 9, 82, 10, then into 38, 27 and 43, 3 and 9, 82 and 10, and finally into seven single items, which are each already sorted. The merge half joins neighbours back together in order: 27, 38 and 3, 43 and 9, 82 and 10, then 3, 27, 38, 43 and 9, 10, 82, and finally the whole list in order: 3, 9, 10, 27, 38, 43, 82.Merge sort on seven items: divide, then merge382743398210382743398210382743398210382743398210273834398210327384391082391027384382DIVIDEinto halvessingle itemsare sortedMERGEin orderMerging two sorted lists only ever looks at the front of each, so it is quick. Splitting costs nothing.
Splitting down to single items is free. All of the work is in the merging.
Python
def merge(left, right):
    result = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i = i + 1
        else:
            result.append(right[j])
            j = j + 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def merge_sort(items):
    if len(items) <= 1:
        return items
    middle = len(items) // 2
    left = merge_sort(items[:middle])
    right = merge_sort(items[middle:])
    return merge(left, right)

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

merge_sort calls itself on each half. That technique is called recursion, and you are not required to write it at GCSE. What you must be able to do is show the splitting down to single items and the merging back up, as in the diagram.

Choosing between them

Bubble sortInsertion sortMerge sort
IdeaSwap neighboursInsert each item into the sorted partSplit, then merge
Easy to writeVeryYesHarder
Big listsVery slowSlowFast
Nearly sorted listFast, with the flagFastSame as any
Extra memoryNoneNoneYes, for the merged copies

Counting the work

Run a bubble sort on a reversed list, so it has the most to do, and count the comparisons as the list gets longer.

Python
def bubble_comparisons(items):
    items = items[:]
    comparisons = 0
    n = len(items)
    for p in range(n - 1):
        for i in range(n - 1 - p):
            comparisons += 1
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
    return comparisons

for n in [10, 20, 40, 80]:
    print(n, "items:", bubble_comparisons(list(range(n, 0, -1))), "comparisons")

Doubling the list from 20 to 40 does not double the work, it quadruples it: 190 comparisons becomes 780. That is why bubble sort is fine for ten names and hopeless for a million. Merge sort's work grows far more slowly.

Compare two sorts with a reason

"Merge sort is faster" earns nothing. "Merge sort is faster on a large list because it does far fewer comparisons, since it halves the list each time, but it needs extra memory for the merged copies" earns three marks.

Merge sort on eight numbers: divide, then mergeMerge sort drawn as a diamond of numbered cards, read from the top down and then back up. The list of eight numbers, 6 3 8 1 7 2 5 4, is divided in half again and again: first into two groups of four, then four groups of two, then eight single cards. A single card is already sorted. Then the groups are merged back together, working upwards. Each merge compares the front card of the two groups and takes the smaller one every time, so the pairs become 3 6, 1 8, 2 7 and 4 5, then the groups of four become 1 3 6 8 and 2 4 5 7, and finally the whole list is merged into 1 2 3 4 5 6 7 8.63817254638172546381725463817254361827451368245712345678dividemerge1 item is sortedto merge:compare thefront of eachgroup, take thesmaller one123
  1. Divide the list in half, again and again.
  2. Stop when every group is a single item. One item is already sorted.
  3. Merge groups back together, taking the smaller front item each time, until one sorted list is left.
Merge sort divides until the pieces are trivial, then does all its real work while merging.

Key terms you must be able to define

Algorithm
A step by step set of instructions for solving a problem.
Linear search
Checking each item of a list in turn, from the start, until the wanted item is found or the end is reached.
Binary search
Repeatedly comparing with the middle item of a sorted list and discarding the half that cannot contain the target.
Bubble sort
A sort that repeatedly compares neighbouring items and swaps them if they are in the wrong order, until a pass makes no swaps.
Insertion sort
A sort that takes each item in turn and inserts it into its correct place in the already sorted part of the list.
Merge sort
A divide and conquer sort that splits a list into single items and merges them back together in order.
Divide and conquer
Solving a problem by splitting it into smaller copies of itself, solving those and combining the answers.
Trace table
A table that records the values of variables at each step of an algorithm.
Pass
One complete run through the list by a sorting algorithm.

Flashcards

Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.

DefineAlgorithm
AnswerA step by step set of instructions for solving a problem.
DefineLinear search
AnswerChecking each item of a list in turn, from the start, until the wanted item is found or the end is reached.
DefineBinary search
AnswerRepeatedly comparing with the middle item of a sorted list and discarding the half that cannot contain the target.
DefineBubble sort
AnswerA sort that repeatedly compares neighbouring items and swaps them if they are in the wrong order, until a pass makes no swaps.
DefineInsertion sort
AnswerA sort that takes each item in turn and inserts it into its correct place in the already sorted part of the list.
DefineMerge sort
AnswerA divide and conquer sort that splits a list into single items and merges them back together in order.
DefineDivide and conquer
AnswerSolving a problem by splitting it into smaller copies of itself, solving those and combining the answers.
DefineTrace table
AnswerA table that records the values of variables at each step of an algorithm.

Reach the top grade on this topic

Sorting and searching questions reward the exact order of events, so practise tracing until it is automatic.

  • State that a binary search needs a sorted list, every time it is mentioned
  • Show the middle position working: (low + high) DIV 2, and which half is discarded
  • Write the state of the whole list after each pass of a bubble sort
  • Say that a sort stops when a pass has no swaps, not when it has done n passes
  • Compare algorithms using number of comparisons and memory, not the word "faster" alone

Mistakes that cost marks here

Avoid these
  • Using a binary search on a list that is not in order.
  • Swapping two items without a temporary variable, so one value is lost.
  • Forgetting to carry on until a pass makes no swaps, and stopping after one pass.
  • Calculating the middle with / and not DIV, which gives a decimal position.
  • Saying a linear search is always slower, when for one search of an unsorted list it is the better choice.
Fun fact

Sorting is thought to have taken up a quarter of all computer time in the 1960s. Which algorithm to use mattered so much that Donald Knuth gave a whole volume of The Art of Computer Programming to it, and it is still the standard reference.

Knowledge check

0 of 10 answered
1What must be true of a list before a binary search can be used?
2A binary search of [2, 4, 6, 8, 10, 12, 14] begins by comparing with which item?
3Which search is the better choice for one search of a short list that is not sorted?
4What does a bubble sort do on each pass?
5What is the list [5, 1, 4, 2, 8] after the first pass of a bubble sort?
6How does a bubble sort know it has finished?
7Which technique does a merge sort use?
8What does an insertion sort do with each item in turn?
9Why is a merge sort quicker than a bubble sort on a very large list?
10Which of these sorts needs extra memory for copies of parts of the list?
Score 0 / 10

Exam-style questions

Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.

18 marks
1The list shown is sorted. Describe the steps a binary search takes to find the value 28.4 marks
Describe
Position0123456
Value391417222835

Mark scheme0 / 4
  • LFinds the middle item, which is 17
  • LCompares 28 with 17 and discards the lower half because 28 is larger
  • LTakes the middle of the remaining items, which is 28
  • LCompares and finds 28, so the search is complete
Model answer

The middle item of the seven is 17, at position 3. 28 is larger than 17, so the lower half and 17 itself are discarded, leaving 22, 28 and 35. The middle of those is 28, which matches, so the search stops and reports that 28 is at position 5.

The marker looks for key phrases. If you said it another way and it is still right, give yourself the mark.
2Write a Python function called linear_search that takes a list and a target and returns the position of the target in the list, or -1 if it is not in the list.4 marks
Write

Mark scheme0 / 4
  • LDefines a function with two parameters, the list and the target
  • LA loop that goes through the positions of the list
  • LCompares each item with the target and returns the position when equal
  • LReturns -1 after the loop, once every item has been checked
Model answer
Python
def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

print(linear_search([4, 8, 15, 16], 15), linear_search([4, 8, 15, 16], 99))

Each position is checked in turn and returned as soon as the item matches. The return of -1 is outside the loop, so it only happens when every item has been checked and none matched. The calls shown print 2 and -1.

The marker looks for key phrases. If you said it another way and it is still right, give yourself the mark.
3Show the contents of the list after each of the first two passes of a bubble sort on the list [6, 2, 9, 4]. State whether a third pass is needed.3 marks
Show

Mark scheme0 / 3
  • LAfter the first pass the list is [2, 6, 4, 9]
  • LAfter the second pass the list is [2, 4, 6, 9]
  • LA third pass is needed to confirm that no swaps are made
Model answer

First pass: 6 and 2 swap to give 2, 6, 9, 4. 6 and 9 are in order. 9 and 4 swap, so the list is [2, 6, 4, 9]. Second pass: 2 and 6 are in order, 6 and 4 swap, giving [2, 4, 6, 9]. Another pass is needed, because the second pass made a swap, and it will confirm there are no swaps so the algorithm can stop.

The marker looks for key phrases. If you said it another way and it is still right, give yourself the mark.
4A programmer must find one name in an unsorted list of 20 names, once. Explain why a linear search is a better choice than sorting the list and then using a binary search.3 marks
Explain

Mark scheme0 / 3
  • LA binary search can only be used on a sorted list
  • LSorting the list takes more steps than one linear search would
  • LThe search is only done once so there is no benefit from sorting
Model answer

A binary search only works on a sorted list, so the names would have to be sorted first. Sorting 20 names takes more comparisons than simply checking all 20 once with a linear search. Because the search is only carried out once, there are no later searches to benefit from the sorted list, so the sorting would be wasted effort.

The marker looks for key phrases. If you said it another way and it is still right, give yourself the mark.
5Compare a merge sort with a bubble sort for sorting a list of one million names.4 marks
Compare

Mark scheme0 / 4
  • LMerge sort needs far fewer comparisons on a large list
  • LBecause it halves the list repeatedly, whereas a bubble sort compares neighbours over many passes
  • LMerge sort needs extra memory to hold the merged lists
  • LBubble sort sorts in place and is simpler to write, but is too slow for a million items
Model answer

A merge sort is much better for a million names because it needs far fewer comparisons. It splits the list in half repeatedly and merges sorted halves, so the work grows slowly as the list grows, where a bubble sort makes many passes comparing neighbours and its work quadruples when the list is doubled. The cost of merge sort is that it needs extra memory for the lists it builds, whereas a bubble sort works in place and is simpler to write, but it would be far too slow for a million items.

The marker looks for key phrases. If you said it another way and it is still right, give yourself the mark.
Machine mark 0 / 18