Bubble sort and merge sort

Overview

How a bubble sort passes through a list and when it stops, how a merge sort splits and merges, traced sorts of short lists, comparison counts, and the strengths of each.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   How does a bubble sort work?

   Model answer

   A bubble sort compares each pair of adjacent items in a list. The pair is swapped if the two items are in the wrong order. Passes through the list repeat until a pass makes no swaps.

2. 2

   How many comparisons does one pass of a bubble sort make on a list of 5 items?

   Model answer

   One pass makes four comparisons. A list of n items has n − 1 adjacent pairs.

3. 3

   What is [6, 2, 9, 4, 1] after the first pass of a bubble sort into ascending order?

   Model answer

   After the first pass the list is [2, 6, 4, 1, 9]. The pass makes three swaps, and the largest value, 9, has moved to the end.

4. 4

   What is [6, 2, 9, 4, 1] after the second pass of a bubble sort into ascending order?

   Model answer

   After the second pass the list is [2, 4, 1, 6, 9]. The two largest values are now in their final places.

5. 5

   A bubble sort stops after a pass with no swaps. How many passes does it take to sort [6, 2, 9, 4, 1]?

   Model answer

   The sort takes five passes. Four passes make swaps and the fifth makes none, which confirms the list is in order.

6. 6

   Why can a bubble sort stop as soon as a pass makes no swaps?

   Model answer

   A pass with no swaps shows that every adjacent pair is already in order. The whole list must therefore be sorted.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.