A2 · Practice questions · Insertion sort and comparing sorts

Key, shift, insert.

Six original Cambridge-style questions on insertion sort and comparing sorting algorithms.

Original questions All questions on this page are original work, written in the Cambridge AS & A Level style. They are not from past papers. They test the same concepts and skills the syllabus rewards.

Keep these straight

Key, shift, insert.

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.

Explain

[4 marks]

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

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

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.

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). ✓

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.

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

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

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

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.

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². ✓

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.

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). ✓

Mark this once you have attempted all six and checked your working. It records a Practiced badge on the topic and adds a one-time bonus. Revealing the solutions alone does not count.