Sort It Out: Three Ways

Now watch them work

You have already met the three sorts this specification requires, and what each one is: bubble comparing neighbours and swapping, merge splitting all the way down and joining back up, insertion growing an ordered run at the front. You do not need any of that again. This is the other half of the topic, and it is the half the specification actually names. The note says you must trace and compare three sorts. Those are two different skills and neither is the definition. ⚠️ Tracing means saying what the list looks like after one pass, or after one merge, rather than describing the idea in general. ⚠️ Comparing means saying which one you would choose for a particular list and on what grounds. Knowing what merge sort is earns one mark. Saying what the list looks like after the second merge, and why you would pick it over insertion sort for a million items, earns the rest.

Words for comparing sorts

None of these are the names of the sorts. They are the words you need in order to say something precise about them.

The three, on three measures

Read down each column for one sort, or across each row to compare all three on one measure. The last row is the one most people never learn.

How to compare two of them

⚠️ "It is faster" is not a comparison. It is an opinion with no grounds attached, and on its own it earns almost nothing however true it happens to be. Name the measure first. There are three worth having ready, and between them they answer nearly every comparison question this topic sets: how much work it does on data that is already nearly in order, how the work grows as the list gets much longer, and whether it can work with the list it already has, or has to build something new alongside it. Then commit. Say which one wins on that measure, and then say what that win costs, because on this topic there is always a price and naming it is what separates a good answer from a confident one. So the shape is: a measure, a winner, a price. Three clauses, and you can write it about any pair of them.

Match each to what one step of it does

The one that needs room

Two of the three sorts rearrange the list where it already sits. One builds new lists as it works. Which is which, and why does it matter?

• Merge sort builds new merged lists so it needs extra memory, while bubble and insertion rearrange the list in place
• Bubble sort needs the extra memory, because it makes so many passes over the list
• All three need roughly the same amount of extra memory
• Insertion sort needs the extra memory, because it holds an item while it moves it

Trace the merge, level by level

A merge sort is run on the list 8, 3, 5, 1. Put the stages into the order they happen.

• The list is split into two pieces: 8, 3 and 5, 1
• Each piece is split again, so every piece now holds a single item
• Pieces are merged in pairs: 8 and 3 become 3, 8, while 5 and 1 become 1, 5
• The two ordered pieces are merged by repeatedly taking the smaller front item
• One ordered list remains: 1, 3, 5, 8

Bubble it, one comparison at a time

Bubble sort the list 3, 1, 2. The highlighted pair is the one being compared right now.

True when the list is already sorted

A list arrives already in order. Select the TWO statements that are true.

• Insertion sort does very little work, because each item is already where it belongs
• Bubble sort can stop after one pass, because that pass makes no swaps
• Merge sort skips its work, because it notices the list is already in order
• All three take the same time regardless of the order the list started in

Complete the comparison paragraph

One _____ of bubble sort carries it from one end of the list to the other, checking each adjacent pair as it goes. A sort that shuffles the existing list about without building a second one is said to work _____. Of the three, the one that needs _____ memory is _____, since it assembles fresh lists as it joins pieces back together. When only a handful of items begin out of position, the sort that has least to do is _____.

Compare them at speed

Five in a row, three lives. Every question names a measure, which is the habit the whole module is training.

Comparisons in one pass

A bubble sort makes one full pass along a list of 6 items, comparing each neighbouring pair exactly once. Work out how many comparisons that single pass makes.

Spot the true sorting comparison facts

Tap the TWO statements that are true.

• Merge sort needs extra memory because it builds new lists as it merges
• Bubble sort can finish early if a pass completes with no swaps
• One pass of bubble sort is always enough to leave the list sorted
• Insertion sort splits the list into single items before rebuilding it

Three sorting choices

Three decisions. Each answer has to carry a reason, not just a name.

• A few thousand records arrive almost in order, with only a handful out of place. Which sort would you choose, and on what grounds?
• A very large list has to be sorted, on a machine with plenty of spare memory. Which sort, and why?
• A classmate writes in their notes: "merge sort is just better". What is missing from that?

Compare the three sorts properly

A friend can name all three sorts but keeps writing "merge sort is faster" and scoring one mark. Write them the answer that would score properly.

• Describe what one pass of bubble sort does, and what tells you the list is finished
• Describe what one step of insertion sort does to the ordered part of the list
• Describe how merge sort gets from a whole list down to single items and back again
• Compare the three on how much work they do when the data is already nearly in order
• Finish by saying which one needs extra memory and why, and what that costs you