Insertion sort

Overview

Growing a sorted section from the left by taking the next item and shifting larger ones right, traced item by item, with the comparison counts that follow from it.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   Describe how an insertion sort works.

   Model answer

   An insertion sort takes each item in turn and places it in its correct position among the items already sorted. Larger items are shifted one place right to make room.

2. 2

   Which part of the list is considered sorted at the start of an insertion sort?

   Model answer

   The first item alone is treated as the sorted part. Every remaining item is then inserted into it one at a time.

3. 3

   An insertion sort is applied to 5, 2, 9, 1, 7. What is the list once 2 has been inserted?

   Model answer

   The list reads 2, 5, 9, 1, 7 once 2 has been inserted. The sorted part now holds 2 and 5.

4. 4

   Give the list 5, 2, 9, 1, 7 as it stands after an insertion sort has placed the value 1.

   Model answer

   The list reads 1, 2, 5, 9, 7 at that point. The sorted part holds 1, 2, 5 and 9, and only 7 is left to place.

5. 5

   How many comparisons does an insertion sort make on the list 5, 2, 9, 1, 7?

   Model answer

   The sort makes seven comparisons in total, made up of 1, 1, 3 and 2. The final list reads 1, 2, 5, 7, 9.

6. 6

   State the best case for an insertion sort and its number of comparisons for ten items.

   Model answer

   The best case is a list already in order, needing nine comparisons for ten items. Each item is compared once with its predecessor and no shifting occurs.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.