Insertion sort and merge sort
Trace insertion and merge sort through each stage, then compare their work and storage needs with simpler methods.
Mapped to the Cambridge IGCSE Computer Science 0265 syllabus for exams in 2029. These original explanations and self-checks are independent study support, not Cambridge papers, official marks or grades. Practical programming is taught with worked code and trace tasks; an executable Python workspace and timed digital-exam simulation are not yet available.
Before you begin
- Use the 2029 syllabus for this course. Cambridge specifies Python 3.10 or higher for programming and digital exams for both components. The syllabus currently identifies this route for 2029 only; confirm later-year availability with Cambridge and your school.
Work on paper. Try each question before revealing help, and explain why your method works.
Quick readiness check
Before insertion sort and merge sort, which statement is the safest starting point?
What you will learn
- Trace insertion sort and merge sort on a given list
- Describe how each algorithm proceeds
- Compare their suitability and efficiency without Big-O notation
Insertion sort grows a sorted section
Insertion sort begins with one item treated as sorted. It takes the next value as a key, shifts larger values in the sorted section one position to the right, then places the key in the gap. Repeat until every value has been inserted.
It is easy to trace and can work well on small or nearly sorted lists, but repeatedly shifting values can take a long time for large unsorted lists. Show the sorted and unsorted regions at each pass to avoid losing a value.
Merge sort divides, sorts and merges
Merge sort splits a list into smaller sublists until each contains one item. It then merges neighbouring sublists by repeatedly selecting the smaller front value, producing larger sorted lists until one complete sorted list remains.
Merge sort has predictable efficient behaviour for large lists but needs extra space for temporary lists and is more complex to implement. When comparing algorithms, state the input size or data condition, work required, memory use and any preconditions rather than using Big-O notation.
Pause and explain
Which habit best checks your understanding of insertion sort and merge sort?
Worked example
Use insertion sort to process [6, 3, 5].
Show the worked solution
- Treat [6] as sorted and take key 3; shift 6 right and insert 3: [3, 6, 5].
- Take key 5; shift 6 right because it is larger.
- Insert 5 in the gap: [3, 5, 6].
Answer Sorted list: [3, 5, 6].
Try a topic test
Choose Easy, Normal or Difficult. Save your answers and open worked review after finishing.
Test this topic →From guided practice to a new situation
Write your answer and reasoning first. Use a hint only if you are stuck. The model solution is for self-checking; your written work is not automatically marked.
Perform insertion sort on [7, 2, 5]. Show the list after inserting each key.
Give me a hint
Keep the left portion sorted and insert each next value in the correct place.
Compare my reasoning
- Start with [7] sorted; insert 2 to get [2, 7].
- Insert 5: shift 7 right, then place 5 after 2.
- The list becomes [2, 5, 7].
After the two insertions: [2, 5, 7].
Look for these in your work
- Sorted portion maintained
- Shift correct
- Final order correct
Merge the sorted lists [1, 6, 9] and [2, 4, 8] into one sorted list.
Give me a hint
Compare the first unused value in each list and take the smaller.
Compare my reasoning
- Take 1, then 2, then 4.
- Next compare 6 and 8; take 6, then 8.
- Append the remaining 9.
[1, 2, 4, 6, 8, 9]
Look for these in your work
- Front values compared
- Order preserved
- Remaining values appended
A list of nearly sorted values must be sorted in place with very limited extra memory. Compare insertion and merge sort for this requirement.
Give me a hint
Consider existing order, extra space and how each method moves data.
Compare my reasoning
- Insertion sort can be efficient when only a few items are out of place and needs little extra storage.
- Merge sort handles large data predictably but uses additional temporary space.
- For a nearly sorted list with a strict memory limit, insertion sort is a suitable choice.
Insertion sort is a better fit for this nearly sorted, low-memory case; the choice depends on input conditions.
Look for these in your work
- Input condition
- Space trade-off
- Contextual choice
Common mistakes
- Overwriting a shifted value instead of moving it.
- Merging lists without comparing their front values.
- Claiming merge sort needs no additional storage.
What can you explain now?
What does merge sort do after splitting a list into single-item lists?
Compare with the explanation
Merges the sorted sublists in order
Each merge compares front values and builds a larger sorted list.
After trying it yourself, choose your next review. This is your self-assessment.
Your review choice appears on Today. Sign in to sync it across devices.
Make it stick
How do insertion and merge sort build sorted lists, and when is each a good fit?
If you needed the solution, close it and solve the problem again from a blank page. A correct answer is stronger when you can explain the reason for each step.