Year 8 · Summer 1

Algorithms: search and sort · Lesson 3 of 5

Insertion sort and merge sort, unplugged

UnpluggedTopic 12 Searching and sorting

Year 8 · Algorithms: search and sort · Lesson 3 of 5

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.

Year 8 · Algorithms: search and sort · Lesson 3 of 5

Success criteria

You have got it when you can say:

  • 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.

Year 8 · Algorithms: search and sort · Lesson 3 of 5

Retrieval starter

Questions from before. Write your answers, then show them.

  1. Last lesson

    Merge sort is fast on big lists. What's its main cost?

    A It needs the list to be sorted firstB It only works on numbersC It needs extra memory for the merged copies

    C. It needs extra memory for the merged copies

  2. Last unit

    What does print("3" + "4") show?

    A 34B An errorC 7

    A. 34

  3. Earlier this year

    In https://www.bbc.co.uk/news, the path is…

    A https://B www.bbc.co.ukC /news

    C. /news

Year 8 · Algorithms: search and sort · Lesson 3 of 5

Key words (1 of 2)

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.

Year 8 · Algorithms: search and sort · Lesson 3 of 5

Key words (2 of 2)

Binary search
Search a sorted list by halving it each step.

The explanation · step 1 of 3

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.

The explanation · step 1 of 3

The maths: Comparisons bubble sort can need

The explanation · step 2 of 3

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].

The explanation · step 3 of 3 · part 1 of 2

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]

The explanation · step 3 of 3 · part 2 of 2

Merge sort (continued)

★Remember

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

Year 8 · Algorithms: search and sort · Lesson 3 of 5

Quick quiz · 1 of 3

A linear search on 50 unsorted items, looking for something that is not there, makes…

  1. A 25 checks
  2. B 50 checks
  3. C 1 check

B. 50 checks

It can only say 'not found' after checking every item: the worst case, n = 50.

Year 8 · Algorithms: search and sort · Lesson 3 of 5

Quick quiz · 2 of 3

Bubble sort compares…

  1. A Neighbours
  2. B The first and last items
  3. C Random pairs

A. Neighbours

Items next to each other, swapping them if they're in the wrong order.

Year 8 · Algorithms: search and sort · Lesson 3 of 5

Quick quiz · 3 of 3

During bubble sort, a whole pass makes no swaps. This means…

  1. A Start again from the beginning
  2. B Do one more pass to be safe
  3. C The list is sorted: stop

C. The list is sorted: stop

No pair was out of order, so the whole list is in order. This is the early stop.

Year 8 · Algorithms: search and sort · Lesson 3 of 5

Exit ticket

Answer on paper before you go. Then check.

  1. Which sort splits the list into single items first?

    A Bubble sortB Insertion sortC Merge sort

    C. Merge sort Split until every piece has 1 item, then merge back in order.

  2. Insertion sort is especially quick when the list is…

    A In reverse orderB Very longC Nearly sorted

    C. Nearly sorted Each item only slides as far as it needs. Nearly sorted means hardly any shifting.