TutorForAll

Technologies K–10 · Years 9–10

Bubble sort against merge sort: counting comparisons as lists grow

Computing Technology 7–10 (NSW, 2022); Digital Technologies: Processes and production skills, Producing and implementing (ACARA v9)

Practical, model not builtLow risk

This site has no interactive model of its own. Where a step or a material names a Concept Studio model, simulation or tool, it has not been built; an external simulation a step names (for example PhET) is not part of this site.

The idea

Bubble sort compares every pair of neighbours on every pass and needs about n²/2 comparisons, while merge sort needs about n log2 n, so the gap between them grows quickly with list size.

What you need

  • Computer with Python 3
  • Spreadsheet for plotting

How to do it

  1. Implement bubble sort (without early exit) and merge sort in Python, each counting comparisons.
  2. Sort the list 100 down to 1 with each and record the comparisons.
  3. Sort the already sorted list 1 to 100 with merge sort and record the comparisons.
  4. Repeat with 1000 down to 1.
  5. Sort 5 random lists of 1000 and record the range of merge sort counts.
  6. Check every output against Python's sorted() and plot comparisons against n.

What you should see

For 100 down to 1, bubble sort makes 4,950 comparisons (100 × 99 ÷ 2) and merge sort 356; merge sort on the sorted 1 to 100 makes 316. For 1000 down to 1, bubble sort makes 499,500 and merge sort 5,044. These merge sort counts are for a top-down merge sort that splits at n // 2 and counts one comparison per step while both halves still hold items; splitting the other way swaps the 100-item counts. A random list of 1000 needs far more merge comparisons than the reversed list, about 8,700 (2,000 random shuffles of the numbers 1 to 1000, run for this entry, gave counts from 8,636 to 8,753 with a mean of 8,707), and never more than the worst case of 8,977, while bubble sort still makes 499,500. Every output matches sorted(). The learner knows it worked when their counts equal these for the fixed lists and their random-list counts sit near 8,700 and below 8,977.

What changes

This activity lists no variables to change, measure and keep the same.

Common misconceptions

Each of these ideas is wrong, and the activity is a chance to test it.

  • All sorting algorithms take about the same time (their growth rates differ).
  • Merge sort is always faster for tiny lists (overheads can make simple sorts fine for a few items).
  • An already sorted list takes no work to sort (the algorithm still has to check it).

Safety card

Low riskLearners carry it out

Hazards

  • None beyond normal computer use

Controls

  • Not applicable

Note

No chemicals or heat.

Curriculum references

The NSW syllabus outcomes and Australian Curriculum v9 codes this activity supports. They are references, not a verified or complete curriculum alignment.

  • Computing Technology 7–10 Syllabus (2022), NESA. Current elective syllabus. Code read from the outcomes page on 2026-09-22.CT5-OPL-01
  • Australian Curriculum v9AC9TDI10P09AC9TDI10P06

Sources

The pages the author read to write this activity.

  1. curriculum.nsw.edu.au/learning-areas/tas/computing-technology-7-10-2022/outcomes
  2. www.csfieldguide.org.nz/en/chapters/algorithms/sorting
  3. docs.python.org/3/howto/sorting.html
  4. www.digitaltechnologieshub.edu.au/plan-and-prepare/scope-and-sequence-f-10/years-9-10

All Concept Studio activities