Community resourceWorksheet

1CP2-CT-5.2 Merging sorted lists with while

Part 2 of 7 · 1CP2-CT-5 · Merge sort, files and authentication

The implementation worksheet, advancing one pointer at a time and dealing with whatever is left over.

Students will:

  • advance the correct pointer after each comparison
  • trace a merge and record the growing output
  • construct a complete merge of two sorted lists
  • decide what merging equal values should produce
  • explain why two remainder loops are needed

Inside: 6 explanation cells, 3 multiple-choice questions, 1 Python task, 1 trace table, 1 fill-in-the-blanks cell and 2 written answers. 15 marks, about 45 minutes.

Series: 1CP2-CT-5 · Merge sort, files and authentication, part 2 of 7.

Shared by Coding PathwayVerified teacher

  • 14 cells
  • About 45 minutes
  • CC BY-SA 4.0
  • Shared 17 Aug 2026

Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Merging two sorted lists with while

The merge stage is a precise pointer algorithm. An index tracks the first unused item in each input list. The output list grows one item at a time and remains sorted.

1. Advance one pointer at a time

Merging two sorted lists with pointerscompare left[i] with right[j]left [4, 11, 18]right [7, 9, 20]i → 4j → 7merged [4]4 is smaller: append 4, then advance i only

If left[i] <= right[j], append left[i] and increase i; otherwise append right[j] and increase j. The comparison loop runs only while both lists still contain unused items. Separate loops then copy any remainder.

Fill in the blanks3 marks
Indexes i and j identify the first gap 1 item in each list. After copying the smaller item, only its gap 2 advances. Remaining items are copied when the other list is gap 3.
  • empty
  • pointer
  • unused
  • unsorted

2. Predict before explaining

left = [3, 8]
right = [5, 9]
i = 0
j = 0
merged = []
while i < len(left) and j < len(right):
    if left[i] <= right[j]:
        merged.append(left[i])
        i = i + 1
    else:
        merged.append(right[j])
        j = j + 1
print(merged)
Multiple choice1 mark

What is printed when this loop ends?

  • A`[3, 5, 8, 9]`
  • B`[3, 5, 8]`
  • C`[3, 8]`
  • D`[5, 9]`
Written answer2 marks

Explain why 9 is not printed and what additional code is needed.

Refer to the loop condition and the remaining item.

Students type their answer here.

Trace table5 marks

Complete the trace as two sorted lists are merged. Record changed values and the growing output.

The trace stops when either input list is exhausted; blank means unchanged. List concatenation is used because the native trace engine records assignment changes explicitly.

Use one row for each pass through the loop. Fill in a box only when that value changes on that row, and leave the rest blank.

ProgramPython
  1. left = [2, 7]
  2. right = [4, 6]
  3. i = 0
  4. j = 0
  5. merged = []
  6. while i < len(left) and j < len(right):
  7. if left[i] <= right[j]:
  8. merged = merged + [left[i]]
  9. i = i + 1
  10. else:
  11. merged = merged + [right[j]]
  12. j = j + 1
  13. print(merged)
Trace table with 8 columns
Rowleftrightijmergedi < len(left) and j < len(right)left[i] <= right[j]Output
1
2
3
4
5
6
7

3. Construct the complete merge

Complete the supplied program. Use one while loop for comparisons and two remainder loops. The input lists are already sorted; your program must not call sort() or sorted().

Coding task5 marks
left = [4, 11, 18]
right = [7, 9, 20]
i = 0
j = 0
merged = []
# Merge the lists using indexes and while loops.

4. Handle equal values

Using <= selects an equal value from the left list first. Both equal values must still appear in the result. A merge must preserve duplicates; sorting does not mean removing them.

Multiple choice1 mark

What should merging [2, 5] and [2, 7] produce?

  • A`[2, 5, 7]`
  • B`[2, 2, 5, 7]`
  • C`[2, 5, 2, 7]`
  • D`[5, 7]`
Written answer2 marks

Give two boundary tests for a merge procedure and state the expected result of each.

Consider empty input and duplicate values.

Students type their answer here.

Multiple choice1 mark

Why are two remainder loops needed?

  • ABoth lists always become empty on the same comparison.
  • BEither list may still contain sorted unused items when the comparison loop stops.
  • CThey remove duplicate values.
  • DThey divide the original list.

Route forward

You can implement and test the merge operation. Next you will move from data held in lists to comma-separated text stored in files.