OCR J277 · Component 2 · Topic 2.1.3e

Sorting Algorithms
Insertion Sort

Pick · Compare · Shift · Insert · O(n) best case

CSZone OCR GCSE Computer Science J277

Learning Objectives

By the end of this video you will be able to...

Describe how insertion sort works — the outer loop picks each element from the unsorted portion; the inner loop finds the correct position by shifting larger elements right; the key is then inserted

Apply insertion sort to a data set — trace every pass, showing the key element, which elements are shifted, and the state of the array after each pass

Identify insertion sort from given code — recognise the four signatures: outer FOR from index 1, key extraction, inner WHILE going left with shift, and the final insert without a TEMP variable

State and compare the efficiency of insertion sort — O(n) best case on sorted data, O(n²) average and worst case — and explain how it compares to bubble sort and merge sort

Avoid the common mistakes — starting the outer loop at index 0, confusing shifts with swaps, and miscounting comparisons in trace questions

⚡ The OCR J277 spec lists three sorts: bubble, merge, and insertion. You need to understand, apply, and identify all three.

Insertion Sort — The Concept

Sorting like a hand of playing cards

DEFINITION

Insertion sort builds a sorted portion of the list from left to right, one element at a time. For each element in the unsorted portion, it finds the correct position in the sorted portion by shifting larger elements one place to the right — then inserts the element into the gap.

THE CARD ANALOGY

Imagine picking up playing cards one at a time. Each new card gets slid left to its correct position among the cards already in your hand. The cards already held are always sorted. This is insertion sort.

SORTED PORTION GROWS LEFT TO RIGHT

After pass 1 (i=1): positions 0–1 are sorted. After pass 2 (i=2): positions 0–2 are sorted. After pass n−1: the whole list is sorted. The sorted boundary moves right by one each pass.

HOW IT DIFFERS FROM BUBBLE SORT

	BUBBLE SORT	INSERTION SORT
Method	Swap adjacent pairs	Shift and insert
Uses TEMP?	Yes (3-line swap)	No — just shift
Inner loop	FOR going right	WHILE going left
Best case	O(n)*	O(n)
Worst case	O(n²)	O(n²)

* Bubble best case O(n) only with swapped-flag optimisation

⚡ Key exam distinction: insertion sort shifts elements — it does NOT swap them. There is no TEMP variable. Bubble sort uses a three-line TEMP swap. This is the single most reliable way to tell them apart in code.

The Algorithm

Insertion sort — step by step

STEP 1 — OUTER LOOP (i = 1 to LEN−1)

→

The outer loop starts at index 1, not 0. The first element (index 0) is treated as already sorted — a list of one element is always in order.

→

Each iteration picks the element at position i. This is the element we need to insert into the correct position in the sorted portion (indices 0 to i−1).

STEP 2 — EXTRACT THE KEY

→

key = data[i] — save the current element before any shifting happens. Shifting will overwrite data[i], so we must save the value first.

→

j = i − 1 — j starts at the last element of the sorted portion and moves left.

STEP 3 — INNER WHILE LOOP (SHIFT)

→

Condition: j ≥ 0 AND data[j] > key. Both conditions must be true. The first stops us going past the start. The second stops when we've found where key belongs.

→

Inside the loop: data[j+1] = data[j] — shift the element one place right. Then j = j − 1 — move left.

STEP 4 — INSERT THE KEY

→

After the WHILE loop, j+1 is the correct position. data[j+1] = key — place the saved key into the gap. No TEMP variable. No swap.

⚡ The inner loop can exit for two reasons: (1) j < 0 — key is smaller than everything, so it goes at index 0. (2) data[j] ≤ key — the key belongs right after position j. In both cases, data[j+1] = key is correct.

Pseudocode & Identification

Insertion sort — pseudocode and signatures

PSEUDOCODE

FOR i = 1 TO LEN(data) - 1 ← ① key = data[i] ← ② j = i - 1 WHILE j >= 0 AND data[j] > key ← ③ data[j + 1] = data[j] ← ④ shift right j = j - 1 END WHILE data[j + 1] = key ← ④ insert END FOR

⚡ The definitive test: look for the three-line TEMP swap — if present, it's bubble sort. If absent, and you see a WHILE loop going left and a final insert after it, it's insertion sort.

FOUR IDENTIFICATION SIGNATURES

① OUTER FOR LOOP STARTS AT INDEX 1

FOR i = 1 TO LEN−1. Starts at 1, not 0. Index 0 is the "already sorted" seed. Bubble sort's outer loop starts at 0. Starting at 1 alone is a strong identifier.

② KEY EXTRACTION — key = data[i]

The element at position i is saved before the inner loop overwrites it. Whatever the variable is named, this extraction is unique to insertion sort.

③ INNER WHILE GOING LEFT — j ≥ 0 AND data[j] > key

A WHILE loop (not FOR) that moves j leftward. The double condition checks both bounds (j ≥ 0) and ordering (data[j] > key). Bubble sort uses a nested FOR going right.

④ SHIFT, NOT SWAP — NO TEMP VARIABLE

data[j+1] = data[j] — one line, moves element right. Then after loop: data[j+1] = key — inserts. No TEMP, no three-line swap.

Applying Insertion Sort

Worked example — [5, 3, 8, 1, 4] — Passes 1 & 2

STARTING ARRAY · ■ sorted ■ key ■ shifting

5

3

8

1

4

sorted portion = [5] (index 0 only)

PASS 1 (i=1) — KEY = 3

Before:

5

3

8

1

4

j=0: data[0]=5 > key=3 → shift 5 right. data[1]=5, j=−1
j=−1: j < 0 → exit WHILE. Insert: data[0] = 3

After:

3

5

8

1

4

Shifts: 1 · Sorted portion: [3, 5]

PASS 2 (i=2) — KEY = 8

Before:

3

5

8

1

4

j=1: data[1]=5 > key=8? No → exit WHILE immediately
Insert: data[2] = 8 (no change — already in place)

After:

3

5

8

1

4

Shifts: 0 · Sorted portion: [3, 5, 8]

PASS 2 — THE NO-SHIFT CASE

When the key (8) is already larger than all elements in the sorted portion, the WHILE loop condition is false immediately — zero iterations. The key stays in place. When ALL passes are like this, the whole sort runs in O(n).

Pass 1: key=3, j starts at 0
  j=0: 5 > 3? Yes → shift 5 to [1], j=−1
  j=−1: j < 0 → exit → insert 3 at [0]

Pass 2: key=8, j starts at 1
  j=1: 5 > 8? No → exit immediately → insert 8 at [2]

⚡ "How many shifts occur in pass 2?" — Zero. The WHILE loop exits immediately because data[j] ≤ key. The element stays at its current position. Still counts as a pass — the outer FOR loop still runs; it just doesn't shift anything.

Applying Insertion Sort

Worked example — [5, 3, 8, 1, 4] — Passes 3 & 4

PASS 3 (i=3) — KEY = 1 · Array: [3, 5, 8, 1, 4]

3

5

8

1

4

j=2: 8>1 → shift 8 → j=1
j=1: 5>1 → shift 5 → j=0
j=0: 3>1 → shift 3 → j=−1
Exit. Insert 1 at [0]

1

3

5

8

4

Shifts: 3 · Sorted: [1, 3, 5, 8]

PASS 4 (i=4) — KEY = 4 · Array: [1, 3, 5, 8, 4]

1

3

5

8

4

j=3: 8>4 → shift 8 → j=2
j=2: 5>4 → shift 5 → j=1
j=1: 3>4? No → exit. Insert 4 at [2]

1

3

4

5

8

Shifts: 2 · Sorted: [1, 3, 4, 5, 8] ✓

FULL PASS SUMMARY — [5, 3, 8, 1, 4]

PASS	KEY	SHIFTS	ARRAY AFTER
1	3	1	[3, 5, 8, 1, 4]
2	8	0	[3, 5, 8, 1, 4]
3	1	3	[1, 3, 5, 8, 4]
4	4	2	[1, 3, 4, 5, 8]

⚡ The outer FOR always runs n−1 times (passes are fixed). The number of shifts per pass varies: zero when key is already in place; up to i shifts when key is smaller than everything in the sorted portion.

Trace Diagram

Exam-style trace — [6, 4, 3, 5]

TRACE TABLE — EACH PASS

PASS	i	KEY	j COMPARISONS	SHIFTS	ARRAY AFTER
1	1	4	j=0: 6>4 ✓	1	[4, 6, 3, 5]
2	2	3	j=1: 6>3 ✓ j=0: 4>3 ✓	2	[3, 4, 6, 5]
3	3	5	j=2: 6>5 ✓ j=1: 4>5 ✗	1	[3, 4, 5, 6] ✓

Pass 1: key=4. 6>4→shift. j=−1. Insert 4 at [0].
Pass 2: key=3. 6>3→shift. 4>3→shift. j=−1. Insert 3 at [0].
Pass 3: key=5. 6>5→shift. 4>5? No. Insert 5 at [2]. ✓

PASS-BY-PASS VISUAL

Start:

6

4

3

5

After pass 1:

4

6

3

5

After pass 2:

3

4

6

5

After pass 3 (sorted):

3

4

5

6

⚡ "How many comparisons in pass 3?" — Two. j=2: 6>5 (true — shift). j=1: 4>5 (false — exit). The false check still counts as a comparison. Always count the final check that exits the loop.

Efficiency

Efficiency — insertion sort

BEST

O(n)

Already-sorted data. The inner WHILE loop never executes — zero shifts every pass. The outer loop still runs n−1 times, giving n−1 comparisons total. Linear time.

AVERAGE

O(n²)

Random data. On average, about half the sorted portion needs shifting per pass. The double-loop structure gives quadratic growth.

WORST

O(n²)

Reverse-sorted data. Every pass requires shifting all elements — pass i needs i shifts. Total: 1+2+…+(n−1) = n(n−1)/2 shifts.

THREE-WAY COMPARISON

	BUBBLE	INSERTION	MERGE
Best	O(n)*	O(n)	O(n log n)
Average	O(n²)	O(n²)	O(n log n)
Worst	O(n²)	O(n²)	O(n log n)
Memory	In-place	In-place	Extra needed
Nearly sorted	Good*	Excellent	O(n log n)

* Bubble best case O(n) only with swapped-flag optimisation

Use insertion sort for small datasets or nearly-sorted data.

Use merge sort for large datasets where speed is critical.

Identify from Code

Identifying insertion sort from given code

RENAMED PSEUDOCODE — "NAME THIS ALGORITHM"

FOR pos = 1 TO LEN(arr) - 1 ← ① current = arr[pos] ← ② back = pos - 1 WHILE back >= 0 AND arr[back] > current ← ③ arr[back + 1] = arr[back] ← ④ shift back = back - 1 END WHILE arr[back + 1] = current ← ④ insert END FOR

Renamed: i→pos, key→current, j→back, data→arr. Same structure — same algorithm.

① FOR pos = 1 TO LEN−1

Starts at 1, not 0. A strong identifier — bubble sort starts at 0.

② current = arr[pos]

Element saved before inner loop. Whatever named (current, key, val, temp), this extraction is unique to insertion sort.

③ WHILE back ≥ 0 AND arr[back] > current

A WHILE loop (not FOR), moving leftward. Double condition. Bubble sort uses a nested FOR going right.

④ SHIFT THEN INSERT — NO TEMP

arr[back+1] = arr[back] (shift, inside loop) then arr[back+1] = current (insert, after loop). No TEMP.

⚡ In an exam: (1) outer loop from 1, (2) a variable saving arr[i] before inner loop, (3) a WHILE going left, (4) no TEMP — answer: insertion sort. Justify with any two features for full marks.

Exam Practice

Insertion sort — exam questions

Question 1 — 4 marks

Apply insertion sort to the list below. Show the state of the array after each pass.

List: [7, 3, 1, 5, 2]

Answer — Q1

Pass 1 (key=3): 7>3→shift. Insert 3 at [0]. [3,7,1,5,2]
Pass 2 (key=1): 7>1, 3>1→2 shifts. Insert 1 at [0]. [1,3,7,5,2]
Pass 3 (key=5): 7>5→shift. 3>5? No. Insert 5 at [2]. [1,3,5,7,2]
Pass 4 (key=2): 7>2, 5>2, 3>2→3 shifts. 1>2? No. Insert 2 at [1]. [1,2,3,5,7] ✓

Question 2 — 2 marks

Describe what happens during a pass of insertion sort when the key element is already in the correct position. What is the significance for efficiency?

Answer — Q2

The inner WHILE loop condition (data[j] > key) is false immediately — zero iterations. The key is written back to data[j+1] — no change. (1 mark) When this happens for all passes, the sort runs in O(n) — n−1 comparisons total. This is the best case: already-sorted data. (1 mark)

Question 3 — 4 marks

The pseudocode below shows a sorting algorithm.
(a) Name the algorithm. (1)
(b) Give two features of the code that identify it. (2)
(c) Give one advantage and one disadvantage compared to merge sort. (2)

FOR n = 1 TO LEN(list) - 1
  val = list[n]
  p = n - 1
  WHILE p >= 0 AND list[p] > val
    list[p + 1] = list[p]
    p = p - 1
  END WHILE
  list[p + 1] = val
END FOR

Exam Answers

Question 3 — answer and mark scheme

Q3 MARK SCHEME

(a) Insertion sort (1 mark)

(b) Any two of: outer FOR loop starts at index 1 (not 0) / variable val = list[n] extracts the key before the inner loop / inner WHILE loop moves leftward (p = p−1) checking list[p] > val / shift without TEMP: list[p+1] = list[p], then insert: list[p+1] = val (1 mark each, max 2)

(c) Advantage: insertion sort is in-place — it needs no extra memory beyond the original array; merge sort requires additional memory to store sub-lists during merging. (1 mark)
Disadvantage: insertion sort has O(n²) worst-case efficiency; merge sort has O(n log n) for all cases — significantly faster for large datasets. (1 mark)

ADVANTAGES OF INSERTION SORT

In-place — no extra memory needed. Only the original array and a single key variable.

O(n) best case — excellent on nearly-sorted or already-sorted data.

Simple to implement — good for small datasets.

DISADVANTAGES OF INSERTION SORT

O(n²) worst case — same as bubble sort. Very slow on large randomly-ordered datasets.

Much slower than merge sort on large data — O(n²) vs O(n log n). The gap grows rapidly with list size.

⚡ "Compare insertion sort and merge sort for efficiency." Insertion sort: O(n) best, O(n²) worst. Merge sort: O(n log n) all cases. For large data, merge sort wins. For small or nearly-sorted data, insertion sort can win.

Common Mistakes

Insertion sort — exam pitfalls

1

Starting the outer loop at index 0

The outer FOR loop must start at i=1. Index 0 is the seed of the sorted portion — a single element, always sorted. Starting at 0 tries to insert data[0] into an empty sorted portion, which is wrong.

2

Confusing shifts with swaps

Insertion sort shifts — one line, no TEMP. Bubble sort swaps — three lines using TEMP. In a trace question, writing TEMP lines for insertion sort will lose marks.

3

Not counting the final (false) comparison

Every time the WHILE condition is checked — including the check that makes it exit — counts as a comparison. In pass 3 of [6,4,3,5]: j=2: 6>5 ✓ (shift); j=1: 4>5 ✗ (exit). That's two comparisons, not one.

4

Shifting in the wrong direction

Insertion sort shifts elements to the right (data[j+1] = data[j]) to create a gap. j moves left. The key goes into the gap created at position j+1.

5

Misidentifying insertion sort as bubble sort

Both use nested loops. Key differentiators: insertion sort has a WHILE inner loop; bubble sort has a FOR inner loop. Insertion sort saves a key variable; bubble sort doesn't. Insertion sort has no TEMP variable; bubble sort requires TEMP.

⚡ In a trace question, always show (1) which element is the key, (2) which elements shift and which direction, and (3) the array state after each pass. Even if you get a comparison count wrong, the trace diagram earns method marks.

Summary

2.1.3e — Insertion Sort

HOW IT WORKS

Outer FOR from i=1. Extract key = data[i]. Inner WHILE: while j≥0 and data[j]>key — shift data[j] right, j−−. After loop: data[j+1] = key. Sorted portion grows left to right. n elements → n−1 passes.

FOUR IDENTIFICATION SIGNATURES

(1) Outer FOR starts at index 1. (2) key/current = data[i] extraction before inner loop. (3) Inner WHILE going left (j≥0 AND data[j]>key). (4) Shift (data[j+1]=data[j]) then insert (data[j+1]=key) — NO TEMP variable.

EFFICIENCY

Best O(n) — already sorted, no shifts. Average O(n²). Worst O(n²) — reverse sorted. In-place. Best choice for nearly-sorted data or small datasets.

KEY NUMBERS — [5,3,8,1,4] EXAMPLE

Pass 1: key=3, 1 shift → [3,5,8,1,4]. Pass 2: key=8, 0 shifts. Pass 3: key=1, 3 shifts → [1,3,5,8,4]. Pass 4: key=4, 2 shifts → [1,3,4,5,8]. Total: 6 shifts.

VS BUBBLE SORT AND MERGE SORT

vs Bubble: both O(n²) worst, but insertion shifts (no TEMP), inner loop is WHILE not FOR. vs Merge: insertion is in-place (merge needs memory) but O(n²) vs O(n log n) — merge wins on large data. Insertion wins on small or nearly-sorted data.

2.1.3e Complete

That's Insertion Sort done!

Next up: 2.2.1a — Variables, Constants & Data Types

📝

MARKED WORKSHEET

CSZone.co.uk

🎯

QUIZ

CSZone.co.uk

📊

SLIDES

CSZone.co.uk

Sorting AlgorithmsInsertion Sort

By the end of this video you will be able to...

Sorting like a hand of playing cards

Insertion sort — step by step

Insertion sort — pseudocode and signatures

Worked example — [5, 3, 8, 1, 4] — Passes 1 & 2

Worked example — [5, 3, 8, 1, 4] — Passes 3 & 4

Exam-style trace — [6, 4, 3, 5]

Efficiency — insertion sort

Identifying insertion sort from given code

Insertion sort — exam questions

Question 3 — answer and mark scheme

Insertion sort — exam pitfalls

2.1.3e — Insertion Sort

That's Insertion Sort done!

Sorting Algorithms
Insertion Sort