Test yourself on Insertion Sort with exam style questions, marked instantly.
Flashcards that come back just before you would forget them.
A revision plan that remembers what you know and shows what to do next.
See which topics you have nailed and which need another look.
Quiz yourself on Insertion SortGet your flashcardsBuild my revision planTrack my progressSorting Cards in Your Hand
Insertion sort is how most people sort playing cards. You pick up one card at a time and slide it into the right place among the cards you are already holding. The cards in your hand are always in order, and the pile still to pick up shrinks each time.
Insertion sort takes the next item and inserts it into its correct place in the sorted part on the left. The sorted part grows by one item each row. Insertion sort is named in the OCR J277 specification only. AQA and Edexcel name bubble sort and merge sort but not insertion sort.
Insertion Sort at a Glance
| Feature | Insertion Sort |
|---|---|
| Method | Take the next item (the key) and insert it into its place in the sorted part |
| Sorted part | Starts as the first item and grows by one each step |
| Shifting | Larger items move one place right to make a gap for the key |
| Extra memory | None: it sorts in place |
| Quickest on | Short lists and lists that are nearly sorted |
| Compared with bubble sort | Usually the better of the two, because it makes fewer moves |
Deep Dive: Insertion Sort Trace
Sort [5, 2, 4, 1] into ascending order. The first item, 5, is the sorted part to begin with.
- Key = 2: 5 is larger, so shift 5 right and insert 2. List: [2, 5, 4, 1]
- Key = 4: 5 is larger, so shift 5 right. 2 is smaller, so stop and insert 4. List: [2, 4, 5, 1]
- Key = 1: shift 5, 4 and 2 right, then insert 1 at the front. List: [1, 2, 4, 5]
A list of 4 items needs 3 steps, because the first item starts as the sorted part. A list of 6 items needs 5 steps.
Deep Dive: Best and Worst Lists
- Already sorted, such as [1, 2, 3, 4]: every key is already in the right place, so nothing shifts. This is the quickest case.
- Nearly sorted, such as [2, 3, 4, 1]: only the last key has to move, but it shifts three items.
- Reverse order, such as [4, 3, 2, 1]: every key shifts past every item in the sorted part. This is the slowest case, with 6 shifts for 4 items.
Memory Trick
Insertion = cards in your hand. Pick the next card, slide the bigger cards along, and drop it into the gap.
The sorted part is always on the left and grows by one each step.
Exam Tips
- Show the list after each step: circle or name the key each time.
- Start correctly: the first item counts as the sorted part, so the first key is the second item.
- Say when it is good: small lists and nearly sorted lists.
- Common mistake: mixing it up with bubble sort. Insertion sort does not swap neighbours repeatedly, it inserts one key at a time.
Make this stick
Signing in gives access to all PrepWise features.