What does sorting mean?
Sorting means arranging items in order. The order can be ascending (small to big, A to Z) or descending (big to small).
Why sort? A sorted list is quicker to search (you can use binary search), easier to read, and makes it easy to find the smallest, biggest or middle value.
An algorithm is a list of exact steps. Different sorting algorithms give the same answer but take different amounts of work.
Bubble sort
Go through the list from left to right. Compare each pair of neighbours. If the left one is bigger, swap them. This is one pass. After the first pass the biggest item has “bubbled” to the end.
Repeat passes. Each pass can stop one place earlier. If a pass makes no swaps, the list is sorted and you can stop early.
repeat
swapped ← false
for i ← 0 to n − 2
if A[i] > A[i+1] then
swap A[i], A[i+1]
swapped ← true
until swapped = falseWorst case: about n²/2 comparisons. Easy to write, slow for big lists.
Insertion sort
Think of the first item as a sorted list of one. Take the next item and move it left past every bigger item, then drop it in. Now the sorted part is one longer. Repeat until the end.
It is fast when the list is almost sorted (few moves), and it works well for small lists. Worst case (list in reverse order): about n²/2 comparisons.
Selection sort and counting sort
Selection sort: find the smallest item in the whole list and swap it into place 1. Find the smallest of the rest and swap it into place 2. Keep going. It always makes about n²/2 comparisons, but at most n − 1 swaps.
Counting sort: useful when values are small whole numbers, like marks out of 10. Make a frequency list: how many 0s, how many 1s, … how many 10s. Then write each value out as many times as it was counted. No comparisons at all!
Merge sort: divide and conquer
Divide: split the list into two halves. Split each half again, until every piece has one item (a list of one is already sorted).
Merge: join two sorted lists by looking at the front item of each and taking the smaller one, again and again.
Example: merge [2, 5] and [1, 8]: take 1, then 2, then 5, then 8 → [1, 2, 5, 8].
A list of n items is halved about log₂ n times, and each level of merging does about n comparisons. So merge sort takes about n log₂ n comparisons. It needs extra memory for the merged lists.
Comparing the algorithms
| Algorithm | Comparisons (big lists) | Extra memory | Good for |
|---|---|---|---|
| Bubble | about n²/2 | none | teaching, tiny lists |
| Insertion | about n²/2 (few if nearly sorted) | none | small or nearly sorted lists |
| Selection | about n²/2 | none | few swaps needed |
| Merge | about n log₂ n | yes | big lists |
For 1,000 items: n²/2 = 500,000 comparisons, but n log₂ n ≈ 10,000. That is why merge sort wins on large data.
Try it: sort cards by hand
Take 8 playing cards (or paper slips with numbers). Sort them three times: with bubble sort, insertion sort and merge sort. Keep a tally of each comparison. Which method used the fewest? Now check your tally with the counters in the 3D free-play step.
Key formulas and definitions
- Bubble / insertion / selection: worst case about n(n − 1)/2 comparisons
- Merge sort: about n log₂ n comparisons
- Bubble sort: after pass k, the last k items are in their final place
- Selection sort: at most n − 1 swaps
- Merge rule: always take the smaller front item of the two lists
- Counting sort: count how often each value appears, then write them out in order
Worked examples
1. Show the first pass of bubble sort on [5, 2, 8, 1, 6].
5>2 swap → [2,5,8,1,6]; 5<8 no swap; 8>1 swap → [2,5,1,8,6]; 8>6 swap → [2,5,1,6,8]. After pass 1: [2, 5, 1, 6, 8]; 8 is in its final place.
2. Use insertion sort on [4, 1, 3, 2]. Show the list after each insertion.
Insert 1 → [1, 4, 3, 2]. Insert 3 → [1, 3, 4, 2]. Insert 2 → [1, 2, 3, 4].
3. Use selection sort on [7, 3, 9, 1]. How many swaps are made?
Smallest is 1 → swap with 7: [1, 3, 9, 7]. Smallest of rest is 3, already in place. Smallest of [9, 7] is 7 → swap: [1, 3, 7, 9]. 2 swaps.
4. Show how merge sort sorts [6, 2, 7, 3].
Split: [6, 2] and [7, 3] → [6] [2] [7] [3]. Merge: [2, 6] and [3, 7]. Merge those: take 2, 3, 6, 7 → [2, 3, 6, 7].
5. Sort the marks [3, 1, 3, 0, 2, 1, 3] (out of 3) with counting sort.
Counts: 0→1, 1→2, 2→1, 3→3. Write out: [0, 1, 1, 2, 3, 3, 3].
6. Bubble sort needs how many comparisons in the worst case for 10 items (without early stop)? How many does merge sort need, roughly?
Bubble: 9 + 8 + … + 1 = 45. Merge: about 10 × log₂10 ≈ 10 × 3.3 ≈ 33 (in fact at most 25 for 10 items).
Common mistakes
- Stopping bubble sort after one pass. One pass only fixes the biggest item.
- In merge sort, sticking the halves together without comparing. Merging must pick the smaller front item each time.
- Thinking selection sort is faster because it makes few swaps; it still makes about n²/2 comparisons.
- Forgetting that a pass with no swaps means bubble sort can stop early.