Sorting Algorithms
Bubble sort and merge sort traced pass by pass, why merge sort wins on large lists, and how to answer the compare question without repeating yourself.
Bubble sort
A bubble sort works through the list comparing each pair of adjacent items and swapping them if they are in the wrong order. Each complete pass through the list is called a pass, and after each pass the largest remaining value has moved to its final position at the end.
The name comes from that behaviour: large values rise to the end of the list like bubbles rising to the surface.
Traced properly
Sorting [5, 3, 8, 1] into ascending order.
Pass 1
| Compare | List after the comparison |
|---|---|
| 5 and 3, swap | 3, 5, 8, 1 |
| 5 and 8, no swap | 3, 5, 8, 1 |
| 8 and 1, swap | 3, 5, 1, 8 |
8 is now in its final position, so the next pass does not need to look at it.
Pass 2
| Compare | List after the comparison |
|---|---|
| 3 and 5, no swap | 3, 5, 1, 8 |
| 5 and 1, swap | 3, 1, 5, 8 |
Pass 3
| Compare | List after the comparison |
|---|---|
| 3 and 1, swap | 1, 3, 5, 8 |
A pass then completes with no swaps at all, which tells the algorithm the list is sorted and it stops.
A bubble sort finishes when a complete pass is made with no swaps. Mentioning this earns a mark, because it is the only way the algorithm knows it is done.
SUBROUTINE bubbleSort(items)
swapped ← True
WHILE swapped = True
swapped ← False
FOR i ← 0 TO LEN(items) - 2
IF items[i] > items[i + 1] THEN
temp ← items[i]
items[i] ← items[i + 1]
items[i + 1] ← temp
swapped ← True
ENDIF
ENDFOR
ENDWHILE
RETURN items
ENDSUBROUTINEWhat is good and bad about it
- Good: very simple to write and understand, and it needs almost no extra memory because items are swapped inside the original list.
- Bad: slow on large lists. Sorting n items takes roughly n squared comparisons, so ten times more data means about a hundred times more work.
- Compare two neighbours, and if they are the wrong way round, swap them.
- Work along the list. A big value is carried all the way to the end.
- After a pass the last item is in its final place, so the next pass can be shorter.
- Repeat until a whole pass makes no swaps.
Merge sort
A merge sort repeatedly splits the list in half until every sub list contains one item, then merges the sub lists back together in order.
A list of one item is by definition already sorted, which is what makes the strategy work. All the actual sorting happens during the merging.
The two phases
Split: divide the list in half, then halve each half, and keep going until every sub list holds a single item.
7 3 9 1 5 2
/ \
7 3 9 1 5 2
/ \ / \
7 3 9 1 5 2
/ \ / \
3 9 5 2Merge: take pairs of sub lists and combine them by repeatedly comparing the front item of each and taking the smaller.
3 + 9 -> 3 9
5 + 2 -> 2 5
7 + 3 9 -> 3 7 9
1 + 2 5 -> 1 2 5
3 7 9 + 1 2 5 -> 1 2 3 5 7 9Look closely at the last merge. Compare 3 and 1, take 1. Compare 3 and 2, take 2. Compare 3 and 5, take 3. Compare 7 and 5, take 5. Compare 7 and nothing left on the right, so take 7 then 9. Six comparisons to merge six items, and that is the pattern: each merge costs roughly as many comparisons as there are items in it.
There are only about log n rounds of merging, because the list can only be halved that many times, and each round costs about n comparisons. Doubling the data therefore roughly doubles the work rather than quadrupling it.
Sorting algorithm visualiser
Run bubble, insertion, merge and quick sort side by side and count the comparisons. This tool needs JavaScript, so turn it on to use it. Everything you need to answer the exam question is explained in the text above.
- Divide the list in half, again and again.
- Stop when every group is a single item. One item is already sorted.
- Merge groups back together, taking the smaller front item each time, until one sorted list is left.
Comparing the two
This comparison is examined almost every year and the marks come from giving different points rather than repeating one point in three ways.
| Bubble sort | Merge sort | |
|---|---|---|
| Method | Repeatedly swaps adjacent items | Splits into single items then merges in order |
| Efficiency on large lists | Poor, roughly n squared comparisons | Good, roughly n log n comparisons |
| Memory used | Very little, sorts in place | More, because sub lists are held in memory during merging |
| Ease of writing | Simple, few lines | More complex, usually recursive |
| Best use | Very small lists, or lists that are almost sorted already | Large lists where speed matters |
How to structure the answer
An examiner wants a genuine trade off, not a preference. The structure that always scores is:
- Merge sort is more efficient on large lists, and say why: it halves the problem instead of walking the whole list on every pass.
- Bubble sort uses less memory, and say why: it swaps items inside the existing list rather than building new sub lists.
- Conclude by naming the condition that decides it: list size and available memory.
On a list of eight items, or on a list that is already nearly in order, a bubble sort finishes almost immediately and needs no extra memory. Blanket statements lose the evaluation marks.
If asked how many passes a bubble sort needs on a list of n items, the answer is at most n minus 1, because after n minus 1 items are in place the last one has nowhere else to be.
Key terms you must be able to define
- Bubble sort
- A sort that repeatedly compares adjacent items and swaps them if they are in the wrong order until a pass produces no swaps.
- Pass
- One complete run through the list by a bubble sort, after which the largest remaining item is in its final position.
- Swap
- Exchanging the positions of two adjacent items, which requires a temporary variable to avoid losing one of the values.
- Merge sort
- A sort that divides the list into single item sub lists and then repeatedly merges pairs of sub lists in order.
- Merge
- Combining two sorted sub lists into one sorted list by repeatedly taking the smaller of the two front items.
- In place
- Sorting that rearranges the original list without needing significant extra memory, as a bubble sort does.
- Divide and conquer
- The strategy of splitting a problem into smaller parts, solving each, and combining the results, as merge sort does.
Flashcards
Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.
Reach the top grade on this topic
The trace marks are free if you are systematic, and the comparison marks are where grades are decided.
Show every pass, not every swap. When asked to show the list after each pass, write the state of the whole list at the end of each complete pass. Writing every individual swap wastes time and often loses the mark because the examiner cannot find the pass boundaries.
Give the reason with the property. "Merge sort is faster" is not a mark. "Merge sort is faster on large lists because halving the list means the number of rounds grows very slowly, while a bubble sort has to walk the whole list once per pass" is two.
Always concede something. An evaluation that says merge sort is better in every way is wrong: it uses more memory and is harder to implement. Naming that cost is what moves an answer into the top band.
- Trace a bubble sort on six items showing the list at the end of each pass
- Trace a merge sort showing both the splitting and the merging stages
- State the stopping condition of a bubble sort
- Give three genuinely different points of comparison between the two algorithms
Mistakes that cost marks here
- Showing the list after each swap rather than after each pass when the question asks for passes.
- Forgetting the temporary variable when describing a swap, which would overwrite one of the two values.
- Saying merge sort sorts each half and then joins them, without explaining that the halving continues until each sub list holds one item.
- Claiming merge sort is better in every respect. It needs more memory and is harder to program.
- Saying a bubble sort finishes after a fixed number of passes. It finishes when a pass completes with no swaps, which may be sooner.
Merge sort was described by John von Neumann in 1945, on the same machine project that gave us the stored program computer. It is still the algorithm behind the sort routines in several standard libraries today, eighty years later.
Knowledge check
Exam-style questions
Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.
- LAdjacent pairs of items are compared
- LIf they are in the wrong order they are swapped
- LThis is repeated for the whole list, which is called a pass
- LPasses continue until a pass is completed with no swaps
A bubble sort starts at the beginning of the list and compares the first two items. If they are in the wrong order it swaps them, then moves along one position and compares the next adjacent pair, continuing to the end of the list. One complete journey through the list is called a pass, and at the end of each pass the largest remaining value has been carried to its correct position at the end. The algorithm then begins another pass, and it keeps going until a whole pass is completed without a single swap being made, which shows that no pair is out of order and the list is sorted.
- LThe list is repeatedly divided in half
- LUntil each sub list contains only one item
- LPairs of sub lists are then merged back together
- LDuring each merge the smaller of the two front items is taken first, so the result stays in order
A merge sort repeatedly divides the list in half, then divides each half in half, and continues until every sub list contains only one item, at which point every sub list is trivially in order. It then merges the sub lists back together in pairs. To merge two sub lists it compares the item at the front of each and takes whichever is smaller, repeating until one sub list is empty and then taking whatever is left in the other. Because both inputs to every merge are already sorted, the merged result is sorted too, and after the final merge the whole list is in order.
- LAfter pass 1 the list is 2, 6, 4, 9
- LAfter pass 2 the list is 2, 4, 6, 9
During the first pass 6 and 2 are swapped to give 2, 6, 9, 4, then 6 and 9 are left alone, then 9 and 4 are swapped, so the list after pass one is 2, 6, 4, 9. During the second pass 2 and 6 are left alone, then 6 and 4 are swapped, so the list after pass two is 2, 4, 6, 9.
- LA bubble sort repeatedly swaps adjacent items, while a merge sort divides the list and merges it back
- LA merge sort is more efficient on large lists
- LBecause halving the list means the number of rounds grows very slowly as the list grows
- LA bubble sort needs roughly n squared comparisons, so doubling the data quadruples the work
- LA bubble sort uses less memory because it sorts in place
- LA merge sort needs additional memory to hold the sub lists while merging
A bubble sort works by repeatedly comparing adjacent pairs of items and swapping any that are in the wrong order, whereas a merge sort divides the list until each sub list holds one item and then merges the sub lists back together in order. On large lists a merge sort is considerably more efficient, because each round of merging halves the number of sub lists, so the number of rounds grows extremely slowly even as the list becomes very large. A bubble sort has to walk the whole list once per pass and may need almost as many passes as there are items, which means roughly n squared comparisons, so doubling the size of the list roughly quadruples the work. The trade off is memory. A bubble sort rearranges items inside the original list and so needs almost no extra memory, while a merge sort has to hold the sub lists it is building as well as the original data. For a small list, or on a device with very little memory, a bubble sort is therefore a reasonable choice, but for a large list where speed matters a merge sort is far better.
- LA bubble sort stops when a pass completes with no swaps
- LAn almost sorted list needs few swaps, so that condition is reached quickly
- LSo the algorithm can finish after only one or two passes rather than n minus 1
A bubble sort does not run a fixed number of passes. It keeps making passes until one complete pass finishes without a single swap, because that shows no adjacent pair is out of order and the list must therefore be sorted. If the list is already almost in order then very few items need swapping, so the algorithm reaches a swap free pass after only one or two passes rather than after the n minus 1 passes it would need in the worst case. This is one of the few situations in which a bubble sort performs well.