Insertion sort

Overview

Recall questions on how insertion sort works, tracing it, the sorted section invariant, best, worst and average-case and space complexity, nearly sorted and arriving data, comparison with bubble sort, stability, and when to choose 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, step by step.

   Model answer

   Treat the first item as a sorted section of one. Take the next item and compare it with the items in the sorted section from right to left, shifting each larger item one place to the right to make a gap, then drop the item into the gap so the sorted section is one longer and still in order. Repeat with each remaining item until the whole list has been absorbed into the sorted section.

2. 2

   What real-world action is an insertion sort modelled on?

   Model answer

   Sorting a hand of playing cards. You hold the cards you have already ordered, pick up the next card, slide it along until it sits between the card below it and the card above it, and insert it there.

3. 3

   Trace an insertion sort on the list 5, 1, 4, 2.

   Model answer

   The sorted section starts as just 5. Take 1: 5 is larger so shift it right and insert 1 before it, giving 1, 5. Take 4: 5 is larger so shift it right, 1 is smaller so stop and insert, giving 1, 4, 5. Take 2: 5 shifts right, 4 shifts right, 1 is smaller so stop and insert, giving 1, 2, 4, 5. The list is now sorted.

4. 4

   What is invariably true of the front part of the list part-way through an insertion sort?

   Model answer

   The items processed so far are in sorted order relative to one another, and they occupy the front of the list. They are not necessarily in their final positions, because a later item may still have to be inserted among them, which pushes some of them further along.

5. 5

   State insertion sort's best-case complexity and the input that produces it.

   Model answer

   O(n), on a list that is already sorted. Each new item is compared once with the item immediately to its left, found to be larger, and left where it is, so there are n minus 1 comparisons and no shifts at all.

6. 6

   State insertion sort's worst-case complexity and the input that produces it.

   Model answer

   O(n squared), on a list in exactly reverse order. Every new item is smaller than everything already sorted, so it must be compared with and shift past every one of them, travelling all the way to the front. The number of shifts is then the maximum possible.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.