A. Programming Concepts and Skills · Algorithm Design and Analysis

Comparing Sorting Algorithms: Counting and Timing

C2.3 A3.4About 75 minutes

Learning goals

I can count the comparisons and moves made by selection, bubble and insertion sort on sorted, random and reversed data.
I can run a fair timing experiment on sorting algorithms and explain the results with Big-O.
I can compare sorts on best, average and worst case, extra memory, stability and adaptivity.
I can recommend a sorting algorithm for a given situation and justify it.

Words to know

comparison sort
A sort that decides the order only by comparing pairs of elements (all the sorts in this course).

swap / move
Exchanging two elements, or copying one element to a new position; the other main cost of a sort besides comparisons.

stable / unstable
A stable sort keeps equal keys in their original order; an unstable sort may not.

adaptive
Faster on input that is already nearly sorted.

early exit (bubble sort)
Stopping bubble sort after a pass with no swaps, because the list is already sorted.

Timsort
The sorting algorithm Python uses: a stable, adaptive mix of merge sort and insertion sort, O(n log n) in the worst case.

Which sort wins?

You know three sorts: selection, bubble and insertion. All three are O(n²). Does that mean they are equally good? No. On a nearly sorted list, one of them is hundreds of times faster than another. On a list where moving data is expensive, a different one wins. Curriculum expectation C2.3 asks you to compare the efficiency of sorting algorithms using run times and computational complexity analysis. Let's run the experiment.

The counting experiment

The program below adds counters to all three sorts. Comparisons count < or > tests between elements. Moves count swaps for selection and bubble sort and shifts for insertion sort. Each sort runs on a copy of the same three inputs of n = 400: already sorted, shuffled (with a fixed random seed so you can reproduce it) and reversed. The bubble sort here has an early exit: if a pass makes no swaps, the list is sorted and it stops.

import random

def selection_sort(a):

comps = moves = 0

n = len(a)

for p in range(n - 1):

smallest = p

for i in range(p + 1, n):

comps += 1

if a[i] < a[smallest]:

smallest = i

if smallest != p:

a[p], a[smallest] = a[smallest], a[p]

moves += 1 # one swap

return comps, moves

def bubble_sort(a):

comps = moves = 0

n = len(a)

for p in range(n - 1):

swapped = False

for i in range(n - 1 - p):

comps += 1

if a[i] > a[i + 1]:

a[i], a[i + 1] = a[i + 1], a[i]

moves += 1

swapped = True

if not swapped: # early exit: already sorted

break

return comps, moves

def insertion_sort(a):

comps = moves = 0

for i in range(1, len(a)):

key = a[i]

j = i - 1

while j >= 0:

comps += 1

if a[j] > key:

a[j + 1] = a[j]

moves += 1 # one shift

j -= 1

else:

break

a[j + 1] = key

return comps, moves

random.seed(2026)

n = 400

shuffled = list(range(n))

random.shuffle(shuffled)

inputs = {"sorted": list(range(n)), "random": shuffled, "reversed": list(range(n, 0, -1))}

for sort in (selection_sort, bubble_sort, insertion_sort):

for name, data in inputs.items():

comps, moves = sort(data[:]) # sort a copy

print(f"{sort.__name__:15}{name:9}{comps:7}{moves:7}")

Its checked output is shown in the next box. Columns: algorithm, input, comparisons, moves. random.seed(2026) makes the shuffle the same every time you run it, so you should see these exact numbers.

selection_sort sorted 79800 0

selection_sort random 79800 395

selection_sort reversed 79800 200

bubble_sort sorted 399 0

bubble_sort random 79610 37839

bubble_sort reversed 79800 79800

insertion_sort sorted 399 0

insertion_sort random 38230 37839

insertion_sort reversed 79800 79800

Output of the program above (checked by running it).

Comparisons for n = 400. Selection sort always makes 400 × 399 ÷ 2 = 79 800, whatever the input. Bubble sort (with early exit) and insertion sort drop to 399 on sorted input. On random input, insertion sort makes about half as many comparisons as the other two.

What the numbers show

Selection sort is not adaptive. It always scans the whole unsorted part: exactly n(n − 1) ÷ 2 comparisons. But it makes very few swaps: at most n − 1 (here 395 on random data, and 200 on reversed data, because each swap puts two elements into place). If moving data is expensive (huge records on a slow disk), that can matter.
Bubble sort with early exit is adaptive: 399 comparisons on sorted data. On random data it is the worst of the three: almost n(n − 1) ÷ 2 comparisons and a swap for every inversion (37 839). A swap is 2 or 3 assignments, more work than an insertion-sort shift.
Insertion sort has the same number of moves as bubble sort's swaps: both equal the number of inversions, 37 839. But each move is one cheap shift, and it needs only about n² ÷ 4 comparisons on random data (38 230, close to 400² ÷ 4 = 40 000).
All three are O(n²) in the worst case (reversed: 79 800 comparisons).

The timing experiment

Counting is machine-independent. Now check that run times tell the same story. This program times the three sorts (without counters) and Python's built-in list.sort() on the same random data, and checks that each one really sorted the list.

import random, time

def selection_sort(a):

n = len(a)

for p in range(n - 1):

smallest = p

for i in range(p + 1, n):

if a[i] < a[smallest]:

smallest = i

a[p], a[smallest] = a[smallest], a[p]

def bubble_sort(a):

n = len(a)

for p in range(n - 1):

swapped = False

for i in range(n - 1 - p):

if a[i] > a[i + 1]:

a[i], a[i + 1] = a[i + 1], a[i]

swapped = True

if not swapped:

break

def insertion_sort(a):

for i in range(1, len(a)):

key = a[i]

j = i - 1

while j >= 0 and a[j] > key:

a[j + 1] = a[j]

j -= 1

a[j + 1] = key

def builtin_sort(a):

a.sort()

random.seed(1)

for n in [1000, 2000, 4000]:

data = [random.random() for _ in range(n)]

row = [str(n)]

for sort in (selection_sort, bubble_sort, insertion_sort, builtin_sort):

copy = data[:]

start = time.perf_counter()

sort(copy)

row.append(f"{(time.perf_counter() - start) * 1000:.1f}")

assert copy == sorted(data) # check it really sorted

print(" ".join(row))

Columns: n, then milliseconds for selection, bubble, insertion and built-in sort. Your times will differ. On one computer: 1000 20.6 36.1 17.8 0.1, 2000 86.1 147.9 77.8 0.2, 4000 319.6 614.3 287.8 0.4.

n	selection (ms)	bubble (ms)	insertion (ms)	list.sort() (ms)
1000	20.6	36.1	17.8	0.1
2000	86.1	147.9	77.8	0.2
4000	319.6	614.3	287.8	0.4

One run of the timing program. Each doubling of n multiplies the three O(n²) times by about 4; the built-in sort's time only about doubles.

Reading the timing table

Each time n doubles, the three O(n²) sorts take about 4 times as long (20.6 → 86.1 → 319.6). Theory and measurement agree.
On random data, bubble sort is slowest and insertion sort fastest, matching the counts (bubble does the most comparisons and the most expensive moves).
Selection sort is close to insertion sort in time even with twice the comparisons, because it does very few swaps. Counting only comparisons does not tell the whole story; count the moves too.
Python's list.sort() is hundreds of times faster. Part of that is because it is written in C, but the bigger reason is its algorithm: Timsort is O(n log n). At n = 4000, n² is 16 000 000 while n log₂ n is only about 48 000. You will build an O(n log n) sort yourself in Merge Sort: Divide and Conquer.

	Selection	Bubble (early exit)	Insertion	Merge sort (coming up)
Best-case comparisons	n(n − 1) ÷ 2	n − 1	n − 1	about ½ n log₂ n
Worst-case comparisons	n(n − 1) ÷ 2	n(n − 1) ÷ 2	n(n − 1) ÷ 2	about n log₂ n
Big-O (worst)	O(n²)	O(n²)	O(n²)	O(n log n)
Moves	at most n − 1 swaps	one swap per inversion	one shift per inversion	about n log₂ n copies
Adaptive?	no	yes	yes (very)	not in the basic version
Stable?	no	yes	yes	yes
Extra memory	O(1)	O(1)	O(1)	O(n)

A summary of the sorts in this course. "Extra memory" is space beyond the array itself.

Selection sort is not stable: a long-distance swap can jump one record over another with the same key. Bubble and insertion sort only move elements past neighbours that are strictly out of order, so they are stable.

Worked example

Recommend a sort

For each situation, recommend selection, bubble or insertion sort (or the built-in sort) and justify it with the analysis.

(a) A list of 50 000 high scores is sorted; each day about 20 new scores are appended at the end and the list must be re-sorted. (b) A microcontroller sorts 8 sensor readings stored in memory that wears out with every write. (c) A Python program must sort 2 million records for a report.

(a) The list is nearly sorted: only about 20 elements are out of place, so there are few inversions. Insertion sort is adaptive: about n comparisons plus a shift per inversion. Each new score shifts at most 50 000 elements, so that is at most about 20 × 50 000 = 1 000 000 moves, far fewer than the 1.25 × 10⁹ comparisons selection sort would make. (Better still: insert each new score into place as it arrives, from Subprograms to Insert and Delete Array Elements.)
(b) n = 8 is tiny, so speed hardly matters, but writes are costly. Selection sort makes at most n − 1 = 7 swaps, the fewest writes of the three. (Insertion and bubble sort could make up to 28 moves.)
(c) n = 2 000 000 is far too big for an O(n²) sort: about 2 × 10¹² comparisons. Use the built-in sort (sorted or list.sort with a key), which is O(n log n) and stable: about 4 × 10⁷ comparisons.

(a) insertion sort (adaptive, few inversions); (b) selection sort (fewest writes); (c) the built-in O(n log n) sort. The right choice depends on the input's order, its size and what operation is expensive.

A fair experiment checklist

Give every algorithm the same input (sort copies: data[:]).
Test several kinds of input (sorted, random, reversed, many duplicates), not only random.
Use a fixed seed so the experiment can be repeated exactly.
Check the output is really sorted; a fast wrong sort is useless.
Grow n by a constant factor and look at the ratios.

Just for fun

Programmers joke about "sleep sort": for each number x, start a timer that waits x seconds and then prints x. Small numbers wake up first, so they print in order!

The catch: it takes as long as the biggest number. Sorting [3, 1, 86 400] takes a full day.

Hands-on activity

Sorting showdown

You need: a computer with Python, and paper or a spreadsheet for the results.

Run the counting program for n = 100, 200 and 400. Make a table of comparisons for each sort and input. Check: does doubling n roughly quadruple the comparisons for random input?
Add a fourth input type: few_swaps, a sorted list with 5 random pairs of neighbours swapped. Predict which sort wins before you run it.
Add a fifth input type: 400 elements with only 3 different values ([random.choice([1, 2, 3]) for _ in range(n)]). Which sort does best now?
Run the timing program with n = 1000, 2000 and 4000, three times each, and keep the smallest time per cell.
Write a short recommendation (5 to 8 sentences) for a friend who has to sort a nearly sorted list of 5000 names, using your evidence. Mention the Big-O, the number of moves and stability.

What to look for: for few_swaps, insertion sort needs only about n comparisons (about 404) and bubble sort about 2n (one pass to fix the swapped pairs, then a pass with no swaps), while selection sort still needs 79 800; in step 3 all three are still O(n²), but equal elements never count as out of order, so there are fewer inversions and bubble and insertion sort make fewer moves than on all-different values.

Your turn

How many comparisons does selection sort make for n = 30 on any input?

Why does selection sort make only 200 swaps on reversed input of 400?

Bubble sort's swaps and insertion sort's shifts were both 37 839 on the random input. Why are they equal?

An O(n²) sort takes 2 s for n = 10 000. Estimate the time for n = 40 000.

Which of the three sorts is unstable? Give a tiny example.

Give two reasons why list.sort() is so much faster than our sorts.

More practice: warm-up

Which sort always makes n(n − 1) ÷ 2 comparisons?

Which two sorts are adaptive?

What is the worst-case Big-O of all three simple sorts?

Why should every algorithm in an experiment sort a copy of the same list?

What does early exit do in bubble sort?

More practice: on your own

How many comparisons does bubble sort with early exit make on [1, 2, 3, 5, 4]?

Sorting 10 000 random numbers, about how many comparisons would insertion sort make on average, and about how many would selection sort make?

A timing table shows times 1.0 s, 4.1 s and 16.3 s for n = 5000, 10 000 and 20 000. Is this consistent with O(n²)? Predict n = 40 000.

You must sort records by city, keeping students within each city in their current (alphabetical) order. Which of the three sorts can you use, and why?

Why does counting only comparisons make selection sort look worse than it is in the timing table?

Challenge

How many inversions does a reversed list of n distinct elements have? Use it to explain why insertion sort's worst case is n(n − 1) ÷ 2 shifts.

For a random permutation, the expected number of inversions is n(n − 1) ÷ 4. Explain why, and check it against the n = 400 experiment.

Any comparison sort needs at least about log₂(n!) comparisons in the worst case, because each comparison has 2 outcomes and there are n! possible orders to tell apart. Estimate log₂(n!) for n = 10 (10! = 3 628 800) and compare it with insertion sort's worst case.

Check your understanding

Quiz

On an already sorted list of n elements, which sort still makes n(n − 1) ÷ 2 comparisons?

An O(n²) sort takes 3 s for 20 000 items. About how long for 10 000 items?

Why is insertion sort usually faster than bubble sort on random data, even though both make one move per inversion?

Which sort makes the fewest writes to the array?

Which practice makes a sorting experiment unfair?

Why is Python's list.sort() much faster than our O(n²) sorts for large n?

For parents and teachers

Big idea: C2.3 asks students to compare sorting algorithms using run times and computational complexity analysis (counting statements, iterations or comparisons). This lesson does both on the same algorithms and inputs, and compares them on adaptivity, moves, stability and memory too. It also uses the A3.4 sort algorithms.

How to help: Ask to see the counting table and the timing table side by side, and ask "Do they agree? Where don't they, and why?" A strong answer mentions moves as well as comparisons.

Common difficulties:

Concluding that all O(n²) sorts are equally good.
Running each sort on the output of the previous one (unfair test).
Ignoring the cost of swaps versus shifts.
Over-reading tiny times. Encourage larger n and repeated runs.