Bubble, merge and insertion sort

Overview

How bubble, merge and insertion sorts work, worked passes through short lists, merging two sorted lists, and how the three sorts compare.

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

   Describe how a bubble sort works.

   Model answer

   A bubble sort compares each pair of adjacent items and swaps them if they are in the wrong order. Passes through the list repeat until a pass makes no swaps.

2. 2

   What is [6, 3, 8, 1] after the first pass of a bubble sort into ascending order?

   Model answer

   The list becomes [3, 6, 1, 8]. The pass swaps 6 and 3, leaves 6 and 8 alone, then swaps 8 and 1.

3. 3

   How many passes does a bubble sort need to put [6, 3, 8, 1] into ascending order?

   Model answer

   The sort needs four passes. Passes two and three give [3, 1, 6, 8] and [1, 3, 6, 8]. The fourth pass makes no swaps, which confirms the list is sorted.

4. 4

   Why does the largest value reach the end of the list after the first pass of a bubble sort?

   Model answer

   The largest value is bigger than everything it meets, so it is swapped along at every comparison. The first pass therefore carries it to the last position.

5. 5

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

   Model answer

   A pass without a single swap proves that each neighbouring pair is in order. Further passes could not change anything.

6. 6

   How does an insertion sort work?

   Model answer

   An insertion sort builds up a sorted section at the start of the list. Each following item is taken in turn and inserted into its correct place in that section.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.