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

Insertion sort and merge sort, unplugged

UnpluggedPresent ▶

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

  • Describe insertion sort: take the next item and slide it into place in the sorted part.
  • Describe merge sort: split the list into single items, then merge them back in order.
  • Merge two sorted lists by comparing only their front items.
  • Compare how insertion sort and merge sort felt, and explain which was faster.

Success criteria

  • I can sort a hand of playing cards with insertion sort and explain each move.
  • I can merge [1, 3, 6, 8] and [2, 4, 5, 7] into one sorted list.
  • I can show the list after each step of insertion sort or merge sort.

Key words

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

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.
Linear search
Check every item in turn.
Binary search
Search a sorted list by halving it each step.

The explanation

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

Bubble sort

Bubble sort: compare neighbours, swap if they're in the wrong order. One trip along is a pass. Stop when a pass makes no swaps.

e.g.Example

[5, 1, 4, 2, 8] → pass 1 → [1, 4, 2, 5, 8] → pass 2 → [1, 2, 4, 5, 8] → pass 3: no swaps, done.

!Watch out

Easy to code, but very slow on big lists.

Insertion sort

Insertion sort: like sorting playing cards. Take the next card and slide it into the right place among the sorted ones.

e.g.Example

[5 | 1, 4, 2, 8] → [1, 5 | 4, 2, 8] → [1, 4, 5 | 2, 8] → [1, 2, 4, 5 | 8] → [1, 2, 4, 5, 8].

Merge sort

Merge sort: split the list in half again and again until every piece has 1 item. Then merge pieces back together in order.

  1. Split: [6, 3, 8, 1] [5, 2, 7, 4]
  2. Split: [6, 3] [8, 1] [5, 2] [7, 4]
  3. Split into singles.
  4. Merge: [3, 6] [1, 8] [2, 5] [4, 7]
  5. Merge: [1, 3, 6, 8] [2, 4, 5, 7]
  6. Merge: [1, 2, 3, 4, 5, 6, 7, 8]
★Remember

To merge, only compare the front item of each list and take the smaller.

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.