# Visualising Sorting With Python - Insertion Sort

In this lesson students will implement an insertion sort in Python and visualise its action using matplotlib.

## Learning objectives

- To understand the mechanics and performance of the insertion sort algorithm

## Learning outcomes

### All students are able to

- Describe the basic mechanics of the insertion sort algorithm

### Most students are able to

- Implement an insertion sort in Python
- Describe the mechanics of the insertion sort algorithm in detail

### Some students are able to

- Critically analyse the performance of the algorithm and identify its weaknesses

## Lesson summary

- Students use matplotlib to visualise a single element being sorted using the algorithm
- Students implement the full sorting algorithm

## Starter

- Insertion sort can easily be visualised using a pack of cards

- Deal out a hand of 5 cards; if you have enough you could deal these out to the students, or to 10 groups at least
- The card on the far left is ignored
- The next card along is left in place if larger, or swapped if smaller
- The next card along is then moved left until it reaches the correct place in the hand
- This can be repeated two more times to order the hand

## Main development

- The students can work their way through the worksheet, slowly building up the insertion sort algorithm until it is complete.

## Plenary

- Have students compare the speed of their bubble sort and insertion sort algorithms
- They can remove their
`display()`

function calls and provide the algorithms with very large lists - 5000 items should do

## Extension

- Have students research optimisation for the insertion sort algorithm