Sorting: bubble sort and insertion sort

Bubble sort

1. Compare the first two items; if they are in the wrong order, swap them.

2. Move along one place and repeat until the end of the list. This is one pass; the largest item has 'bubbled' to the end.

3. Repeat passes, each one stopping one place earlier.

4. Stop when a pass makes no swaps (the list is sorted).

Sorting 5, 1, 4, 2, 8: 4 swaps in total; the final pass has no swaps, so the sort stops.

Insertion sort

1. Treat the first item as a sorted section of length 1.

2. Take the next item and compare it with items in the sorted section, moving larger items one place right, until its correct position is found; insert it there.

3. Repeat until every item has been inserted.

Sorting 6, 3, 9, 1, 5.

Comparing them

• Both are simple, sort the list in place (little extra memory) and are fine for small lists.
• Both need about n²/2 comparisons in the worst case (reverse order), so they are slow for large lists.
• Insertion sort is usually faster in practice, and very fast on lists that are already nearly sorted.
• Bubble sort with the 'no swaps' check can detect a sorted list in one pass.

Worked example

Show the first pass of a bubble sort on 9, 4, 7, 3.

1. Compare 9 and 4: swap, giving 4, 9, 7, 3
2. Compare 9 and 7: swap, giving 4, 7, 9, 3
3. Compare 9 and 3: swap, giving 4, 7, 3, 9

Answer: After pass 1: 4, 7, 3, 9

Check yourself

1. Give the list after the first pass of a bubble sort (ascending) on 7, 2, 9, 4, 3. Separate items with commas.
   Show answer

   2, 7, 4, 3, 9. After pass 1: 2, 7, 4, 3, 9; 9 has moved to the end.

2. How many swaps does a bubble sort make in total to sort 9, 4, 7, 3 into ascending order?
   Show answer

   5. Pass by pass: 4, 7, 3, 9 / 4, 3, 7, 9 / 3, 4, 7, 9; total swaps 5.

3. Bubble sort with the no-swaps check is used on 5, 1, 4, 2, 8. How many passes are made in total?
   Show answer

   3. Passes: 1, 4, 2, 5, 8 / 1, 2, 4, 5, 8 / 1, 2, 4, 5, 8. The last pass makes no swaps.

4. Give the list after the first two items have been inserted by an insertion sort on 4, 2, 7, 1, 3 (that is, after inserting 2 and then 7).
   Show answer

   2, 4, 7, 1, 3. Insert 2: 2, 4, 7, 1, 3; insert 7: 2, 4, 7, 1, 3.

5. Give the list after inserting the item 1 in an insertion sort on 4, 2, 7, 1, 3 (after 2, 7 and 1 have been inserted).
   Show answer

   1, 2, 4, 7, 3. 2, 4, 7, 1, 3 becomes 1, 2, 4, 7, 3: 1 moves past 7, 4 and 2.

6. When does a bubble sort with the no-swaps check stop?
   • After exactly one pass
   • After a pass in which no swaps were made
   • When the first item is the smallest
   • When the middle item is found
   Show answer

   After a pass in which no swaps were made. No swaps means every pair is in order.

7. Which sort is especially efficient on a list that is already nearly sorted?
   • Bubble sort without a no-swaps check
   • A sort that compares every pair of items regardless of order
   • Binary search
   • Insertion sort
   Show answer

   Insertion sort. Each item needs to move only a little, so few comparisons and shifts.

8. In the worst case, bubble sort makes (n - 1) + (n - 2) + ... + 1 comparisons. How many is that for n = 8?
   Show answer

   28. 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary/Advanced Level in Computer Science specification (2026)
• Pearson Edexcel IAL Computer Science IAS sample assessment materials (Unit 1, WCP01)

Last updated 8 November 2026. Spotted a mistake? Tell us.