Insertion sort and comparing sorts pack

At a glance

The shape of the lesson

Topic

Computational thinking and problem-solving

Syllabus reference

Cambridge International AS and A Level Computer Science 9618, 19.1

Level

A Level (A2)

Duration

45 minutes, lab-led; stretches to a 60 minute block (see the contingency notes)

Position in topic

Lesson 2 of 5 in Computational thinking and problem-solving; follows Binary search; leads into Stacks, queues, linked lists and binary trees

Central model

Fig. 1: an insertion sort of five integers, shown after each pass; 8 comparisons in total

Cooperative structure

Think-Pair-Share

Assessment

Stage 1 check and the exam-style plenary from the student lesson, plus the worksheet as the exit task

Learning objectives

By the end of the lesson, learners can

Section by section

Build a sorted part: In the lab, step through an insertion sort.
Write it in pseudocode: The outer FOR loop chooses the key; the inner WHILE loop shifts larger items right.
Which sort, and when?: The syllabus says the performance of a sorting routine may depend on the initial order of the data and the number of items.

Key points to leave on the board

Outer loop: FOR i ← 2 TO n, Key ← List[i], j ← i - 1.
Inner loop: while j >= 1 and List[j] > Key, shift right and decrease j.
Insert: List[j + 1] ← Key after the inner loop.
Performance: n − 1 comparisons if sorted, n(n − 1)/2 if reversed; O(n²) worst case.

The core visual model

One picture every idea returns to

An insertion sort treats the first element as a sorted part of length one. Each pass takes the next element as the key, compares it with the sorted part from right to left, shifts every larger element one place to the right, and drops the key into the gap. After pass i the first i elements are in order. On data that is already sorted each pass makes one comparison, so it needs only n − 1 comparisons; on data in reverse order it needs n(n − 1)/2. The bubble sort has the same best and worst cases, but usually makes more comparisons and moves data with three-step swaps.

Fig. 1: an insertion sort of five integers, shown after each pass; 8 comparisons in total

Lesson sequence

Forty-five minutes, phase by phase

Time	Phase	What happens in the room	Grouping
0 to 5 min	Hook: predict	Open with the question in the title, Slide it into place.. An insertion sort builds a sorted part at the front of the list, taking the next item each time and sliding it back to where it belongs. Put the figure on the board: it is the one picture every idea in the lesson returns to.	Whole class, then pairs
5 to 13 min	Teach and check: Build a sorted part	In the lab, step through an insertion sort. Project tab 4 of the lab (Insertion sort) and let a student drive it while the class predicts. Model the worked example One pass in detail on the board, one line at a time. Your turn: Do the final pass: insert the key 19 into 8, 12, 27, 35. How many comparisons are made?	Whole class, then pairs
13 to 21 min	Teach and check: Write it in pseudocode	The outer FOR loop chooses the key; the inner WHILE loop shifts larger items right. Model the worked example Full trace on the board, one line at a time. Your turn: A 4-element array holds 4, 9, 2, 7. What does it hold after the pass with i = 3, and how many comparisons does the whole sort make?	Pairs
21 to 30 min	Teach and check: Which sort, and when?	The syllabus says the performance of a sorting routine may depend on the initial order of the data and the number of items. Project tab 5 of the lab (Comparing algorithms) and let a student drive it while the class predicts. Model the worked example Predict the work on the board, one line at a time. Your turn: How many comparisons does an insertion sort make on 10 items in reverse order? And on 10 items already sorted?	Think-Pair-Share
30 to 36 min	Check	The four Stage 1 questions from the student lesson, answered on mini whiteboards or by show of fingers. Re-teach the one most get wrong.	Individual, then whole class
36 to 43 min	Plenary	The exam-style questions from Stage 2, one at a time: thirty seconds alone, then a random call. The feedback lines in the key give the examiner's wording.	Individual, random call
43 to 45 min	Exit and homework	Set the worksheet below (6 questions, 23 marks). Learners self-assess against the objectives before they leave.	Individual

Timing and contingency

Protect the parts that carry the learning

The sequence carries about fifty minutes of material, so the lab is driven by one student while the class predicts rather than explored freely. Times are a guide.

Protected: the check at 30 minutes. It is the only individual read on whether the key idea landed, and it is not cut.

Cut first if the build overruns: the last check in Which sort, and when?, never the check or the plenary.

In a 60 minute block: run worksheet questions 1 to 3 in class as a Rally Coach set and model both the hardest worked example and its check live.

Running the cooperative task

Think-Pair-Share

Pose the question, give thirty seconds of silent thinking, then a minute to compare with a partner before a few pairs share with the class. The silent minute is the part that cannot be cut.

The full structure, with its variations and the other twelve, is on the cooperative-learning page.

Examiner traps to pre-empt

What to head off, and how

Trap learners fall into	Teaching move that pre-empts it
Do not describe an insertion sort as "comparing adjacent pairs and swapping them": that is a bubble sort.	Say that each item is inserted into its correct position in the sorted part.
Writing List[j] ← Key after the loop puts the key one place too far left.	When the loop stops, j points at the element that is not larger, so the gap is at j + 1.
"Insertion sort is faster than bubble sort" earns little on its own.	Link the answer to the data: for nearly sorted data both are quick, and in the worst case both need n(n − 1)/2 comparisons.

Worksheet

Insertion sort and comparing sorts: worksheet

6 questions, 23 marks. Written in the style of the papers; no past paper question is reproduced.

NameClassDate

Q1 · explain[4 marks]

Describe how an insertion sort puts an array of integers into ascending order.

Q2 · trace[4 marks]

Using the insertion sort in this lesson (adapted for 5 elements), show the contents of the array after each pass when it starts as 31, 18, 24, 5, 40.

Q3 · write[6 marks]

Names : ARRAY[1:200] OF STRING is a global array. Write pseudocode for a procedure SortNames() that uses an insertion sort to put the names into alphabetical order.

Q4 · calculate[3 marks]

Calculate the number of comparisons an insertion sort makes on 20 items (a) already in ascending order (b) in descending order. Show your working for (b).

Q5 · analysis[4 marks]

A shop keeps a sorted array of 5000 product records. Each evening about 10 new records are added at the end and the array is sorted again. Explain why an insertion sort is a good choice here, and how its performance would change if the array were in reverse order.

Q6 · explain[2 marks]

Both the insertion sort and the bubble sort are described as sorting in place. Explain what this means for the memory they use.

Answer key and marking notes

Q1 · 4 marks

The first element is treated as a sorted list; each following element in turn is taken as the key.
The key is compared with the elements of the sorted part, starting from the one immediately to its left.
Each element larger than the key is moved one place to the right.
The key is inserted into the gap when an element not larger than it (or the start of the array) is reached; repeat until the last element has been inserted.

Q2 · 4 marks

After i = 2: 18, 31, 24, 5, 40.
After i = 3: 18, 24, 31, 5, 40.
After i = 4: 5, 18, 24, 31, 40.
After i = 5: 5, 18, 24, 31, 40 (40 is not moved).

Q3 · 6 marks

Procedure header and ENDPROCEDURE, with local variables declared (i, j, Key : STRING).
FOR i ← 2 TO 200 ... NEXT i.
Key ← Names[i] and j ← i - 1 at the start of each pass.
WHILE j >= 1 AND Names[j] > Key (or an equivalent flag-based loop).
Inside the loop Names[j + 1] ← Names[j] and j ← j - 1.
After the loop Names[j + 1] ← Key.

Q4 · 3 marks

(a) 19.
(b) 1 + 2 + ... + 19 = 20 × 19 / 2.
= 190 comparisons.

Q5 · 4 marks

The data is nearly sorted: the 4990 existing records are already in order.
Insertion sort makes one comparison for each record already in place, and only the 10 new keys move back, so the work is close to n − 1 comparisons (O(n)).
A plain bubble sort makes every pass in full, and even the improved version needs one pass for each place a small new key must move back to the front.
In reverse order every key moves to the front: n(n − 1)/2 = 12 497 500 comparisons, so the time grows with n².

Q6 · 2 marks

The data is rearranged inside the original array; no second copy of the list is made.
Only a fixed number of extra variables (such as Key or Temp and loop counters) is needed, whatever the number of items (O(1) extra space).

Quiz

6 multiple-choice questions on this lesson

From the topic question bank. Assign them in the app for a marked score in your gradebook, or run the topic as a class game.

Assign in the app Run as a class game Topic question bank

Q11 mark

List : ARRAY[1:5] OF INTEGER holds 23, 11, 30, 7, 18 and is sorted by this insertion sort.

FOR i ← 2 TO 5
    Key ← List[i]
    j ← i - 1
    WHILE j >= 1 AND List[j] > Key
        List[j + 1] ← List[j]
        j ← j - 1
    ENDWHILE
    List[j + 1] ← Key
NEXT i

What does List hold at the end of the pass with i = 4?

A7, 11, 23, 30, 18
B11, 23, 30, 7, 18
C7, 11, 18, 23, 30
D7, 23, 11, 30, 18

Q21 mark

List : ARRAY[1:5] OF INTEGER holds 23, 11, 30, 7, 18 and is sorted by this insertion sort.

FOR i ← 2 TO 5
    Key ← List[i]
    j ← i - 1
    WHILE j >= 1 AND List[j] > Key
        List[j + 1] ← List[j]
        j ← j - 1
    ENDWHILE
    List[j + 1] ← Key
NEXT i

How many times is the comparison List[j] > Key evaluated in total?

Q31 mark

An insertion sort is run on 20 items that are already in ascending order. How many comparisons does it make?

A19
B20
C190
D400

Q41 mark

This insertion sort sorts List : ARRAY[1:5] into ascending order.

FOR i ← 2 TO 5
    Key ← List[i]
    j ← i - 1
    WHILE j >= 1 AND List[j] > Key
        List[j + 1] ← List[j]
        j ← j - 1
    ENDWHILE
    List[j + 1] ← Key
NEXT i

Which single change makes it sort into descending order?

AChange List[j] > Key to List[j] < Key
BChange FOR i ← 2 TO 5 to FOR i ← 5 TO 2 STEP -1
CChange j ← i - 1 to j ← i + 1
DChange List[j + 1] ← Key to List[j - 1] ← Key

Q51 mark

List : ARRAY[1:4] OF INTEGER holds 2, 8, 5, 9. A student writes this insertion sort.

FOR i ← 2 TO 4
    Key ← List[i]
    j ← i - 1
    WHILE j >= 1 AND List[j] > Key
        List[j + 1] ← List[j]
        j ← j - 1
    ENDWHILE
    List[j] ← Key
NEXT i

What does List hold after the pass with i = 2?

A8, 8, 5, 9
B2, 8, 5, 9
C2, 2, 5, 9
D8, 2, 5, 9

Q61 mark

An insertion sort takes 0.5 seconds to sort 3000 records that are in reverse order. About how long will it take to sort 12 000 records in reverse order on the same computer?

A8 seconds
B2 seconds
C4 seconds
D32 seconds

Quiz key

Q1: A

Pass 2 gives 11, 23, 30, 7, 18 and pass 3 leaves it unchanged. In pass 4 the key 7 is smaller than 30, 23 and 11, so all three shift right and 7 goes into element 1: 7, 11, 23, 30, 18. 11, 23, 30, 7, 18 is the list before pass 4, 7, 11, 18, 23, 30 is the list after pass 5, and 7, 23, 11, 30, 18 swaps 7 with the first element as a selection sort might, instead of shifting.

Q2: A

Pass 2: 1 (23 > 11). Pass 3: 1 (23 > 30 is FALSE). Pass 4: 3 (30, 23 and 11 are all larger, then j = 0). Pass 5: 3 (30 and 23 larger, 11 > 18 FALSE). Total 1 + 1 + 3 + 3 = 8. 10 is the worst case n(n − 1)/2 for 5 items, 6 is the number of shifts, and 4 is the number of passes.

Q3: A

There are n − 1 = 19 passes and each makes a single comparison that is FALSE, so 19 comparisons: the O(n) best case. 20 counts a pass for the first element, which is never a key, 190 is the reverse-order worst case n(n − 1)/2, and 400 is n².

Q4: A

Shifting items that are smaller than the key leaves larger items in front, so the sorted part builds in descending order. Running the outer loop backwards still sorts ascending (and starts from a sorted part that does not exist), j ← i + 1 looks at the unsorted part, and List[j - 1] ← Key writes the key in the wrong place and loses data.

Q5: A

Key ← 8 and j ← 1. List[1] = 2 is not greater than 8, so the loop does not run and j stays 1. The faulty line writes 8 into List[1], overwriting 2: the list becomes 8, 8, 5, 9 and the value 2 is lost. The correct code writes to List[j + 1] = List[2] and leaves 2, 8, 5, 9. 2, 2, 5, 9 would need a shift that never happened, and 8, 2, 5, 9 is a swap, which this code never does.

Q6: A

In the worst case the comparisons are n(n − 1)/2, which grows with n². 12 000 is 4 times 3000, so the work is about 4² = 16 times as much: 0.5 × 16 = 8 seconds. 2 seconds assumes linear growth (the best case on sorted data), 4 seconds multiplies by 8, and 32 seconds multiplies by 4³ as if the sort were O(n³).

Lab and demo

What to project

The student lesson embeds these tabs. Open them full screen on the projector; every slider has a drag handle on the stage.

Tab 4Insertion sort Tab 5Comparing algorithms

Slides

Slides for this lesson

A projectable deck for every pack is on the way. Until then, present the student lesson full screen: its sections, figure and lab tabs follow the same order as the plan above.

Also for this topic

Everything else you can use

Student lessonInsertion sort and comparing sorts Practice pageWorked solutions, reveal one at a time Topic question bankEvery MCQ for Computational thinking and problem-solving Revision notesOne page per lesson, with the traps Notes PDFPrint the topic notes Topic planComputational thinking and problem-solving: every lesson in order

Original work by the TheLucidSTEM team. The worksheet items are written in the style of the papers; no past paper question is reproduced.