Key Terms
- Insertion sort: Inserts each item into its correct place in the sorted part of the list
- Sorted part: The items at the start of the list that are already in order
- Key: The item currently being placed
- Shifting: Moving larger items one place right to make a gap
- In place: Sorts without needing a second list
- Nearly sorted list: A list that is almost in order, where insertion sort is quickest
Must-Know Facts
- The sorted part starts with just the first item
- The sorted part is at the start (left) of the list and grows by one each step
- Insertion sort is quickest on nearly sorted lists
- A reverse order list is the slowest case
- It sorts in place and needs no extra memory
- It is usually better than bubble sort
Key Concepts
- Take the next item (the key), compare it leftwards, shift larger items right, insert the key
- The key stops moving when it meets a smaller item or reaches the start
- The unsorted part on the right shrinks each step
- In exams: show the list after each key is inserted
Common Mistakes
- Confusing it with merge sort: Insertion sort works along the list. It does not split it in half
- Confusing it with bubble sort: Bubble sort swaps neighbours in passes. Insertion sort inserts one key into the sorted part
- Always putting the key at the front: The key goes where it fits, which is only the front if it is smaller than every sorted item
- Starting with an empty sorted part: The first item is already the sorted part
- Thinking reverse order is quickest: A nearly sorted list is quickest, and a reverse order list is the slowest
This topic summary covers Knowledge Organiser: Insertion Sort within Insertion Sort for GCSE Computer Science. Revise Insertion Sort in 3.1 Fundamentals of Algorithms for GCSE Computer Science with 15 exam-style questions and 10 flashcards. This topic appears regularly enough that it should still be part of a steady revision cycle. It is section 7 of 7 in this topic. Use this topic summary to connect the idea to the wider topic before moving on to questions and flashcards.
Practice questions for Insertion Sort
Which statement best describes how insertion sort works?
Describe how insertion sort works. Your answer should include how the algorithm processes each element.
Quick recall flashcards
How does insertion sort work?
Builds sorted list one element at a time by inserting each element into its correct position
What is the time complexity of insertion sort?
O(nĀ²) worst/average case, O(n) best case (already sorted)