Skip to the page
Year 8 · Summer 1 · Algorithms: search and sort

Comparing efficiency by counting comparisons

TheoryPresent ▶

What this lesson covers

Topic 12 Searching and sorting

KS3 Computing · Searching finds an item. Sorting puts items in order. Some algorithms are hugely faster than others on big lists, and the difference grows as the list grows.

Computational ThinkingCambridge Lower Secondary Computing 0860

You will learn to

  • Count the comparisons a search or a sort makes on a short list.
  • Compare how the number of comparisons grows when the list doubles in length.
  • Explain that n² grows much faster than n log n as the list gets longer.
  • Choose an algorithm for a situation: sorted or not, big or small.

Success criteria

  • I can fill in a table of comparisons for lists of 8, 16 and 32 items.
  • I can say that doubling a list adds only one check to a binary search.
  • I can choose a search or a sort for a scenario and give a reason.

Key words

Say each word, then read what it means. Every one is in the glossary too.

Linear search
Check every item in turn.
Binary search
Search a sorted list by halving it each step.
Bubble sort
Swap neighbours until a whole pass makes no swaps.
Insertion sort
Slide each item into its place in the sorted part.
Merge sort
Split into single items, then merge back in order.

The explanation

Read it here, or open the study page below to go one step at a time with things to try.

Comparing them

AlgorithmNeeds sorted?Speed on big listsEasy to code?
Linear searchNoSlowVery
Binary searchYesVery fastFairly
Bubble sort—Very slowVery
Insertion sort—Slow (fast if nearly sorted)Fairly
Merge sort—Fast (uses extra memory)Harder
★Remember

There's rarely one best algorithm, only the best one for this data.

Study it

Open the study page and go one step at a time.

Topic 12 · Year 8

Searching and sorting

Searching finds an item. Sorting puts items in order. Some algorithms are hugely faster than others on big lists.

Check yourself

One question at a time. The reason shows after each answer.

Saved on this device.