Insertion sort and merge sort
Insertion sort
An insertion sort treats the first item as a sorted list of one.
Each pass takes the next item and slides it left into the right place in the sorted part.
- Pass 1 inserts the second item, pass 2 the third, and so on: a list of n items takes n − 1 passes.
- Items in the sorted part that are bigger than the new item each move one place right.
- It is quick when the list is already nearly in order.
A worked example: an insertion sort on 31, 8, 19, 4, 26, into ascending order.
- Start: the sorted part is just 31. The list is 31, 8, 19, 4, 26.
- Pass 1 inserts 8. 31 is bigger than 8, so 31 moves one place right and 8 goes in front: 8, 31, 19, 4, 26.
- Pass 2 inserts 19. Only 31 is bigger, so 1 item moves right: 8, 19, 31, 4, 26.
- Pass 3 inserts 4. 8, 19 and 31 are all bigger, so 3 items move right: 4, 8, 19, 31, 26.
- Pass 4 inserts 26. Only 31 is bigger, so 1 item moves right: 4, 8, 19, 26, 31. Sorted after 4 passes.
After pass k, the first k + 1 items are in order and the items after them have not moved yet. That is how you can tell an insertion sort from a bubble sort: a bubble sort moves the largest item to the end in its first pass.
Merge sort
A merge sort splits the list into single items, then merges them back together in order.
It has two stages.
- Split the list in half, and split each half again, until every list holds one item. A list of one item is sorted.
- Merge neighbouring lists into one sorted list: compare the front items, take the smaller, repeat.
- Keep merging, pairs into fours, fours into eights, until one sorted list is left.
In this course, when a list has an odd number of items, the left half takes the extra one. A question usually shows you how the list was split; follow what they show.
When you merge two lists and one runs out, copy the rest of the other across without comparing.
A worked example: merge [5, 23, 40] and [12, 18, 51]. Each step compares the two front items and takes the smaller one.
- 5 vs 12: take 5. Merged so far: 5.
- 23 vs 12: take 12. Merged so far: 5, 12.
- 23 vs 18: take 18. Merged so far: 5, 12, 18.
- 23 vs 51: take 23. Merged so far: 5, 12, 18, 23.
- 40 vs 51: take 40. The first list has run out.
- Copy 51 across without comparing: 5, 12, 18, 23, 40, 51. That is 5 comparisons.
The rounds of merging, for 8 items such as 61, 14, 35, 9, 70, 22, 48, 3:
- Split down to single items: [61] [14] [35] [9] [70] [22] [48] [3].
- Round 1 merges neighbours into pairs: [14, 61] [9, 35] [22, 70] [3, 48].
- Round 2 merges pairs into fours: [9, 14, 35, 61] [3, 22, 48, 70].
- Round 3 merges the fours into one sorted list: 3, 9, 14, 22, 35, 48, 61, 70.
The split never changes the order of the items: it only cuts the list into pieces. The left half of [61, 14, 35, 9, 70, 22, 48, 3] is [61, 14, 35, 9].
Comparing the three
| Bubble sort | Insertion sort | Merge sort | |
|---|---|---|---|
| How it works | Swap neighbours, pass after pass | Slide each item into a sorted part | Split, then merge in order |
| Long random list | Slow | Slow | Fast |
| Nearly sorted list | Fairly quick (stops early) | Quick | No faster |
| Extra memory | Very little | Very little | More, for the merged lists |
| Ease of writing | Easy | Easy | Harder (often recursive: the code calls itself on each half) |
Merge sort needs extra memory because it builds new lists while it merges. Bubble sort and insertion sort sort the list where it is, so they need very little extra memory.
To write these in Python, see Insertion sort and merge sort on Brainlag Code.