Week 09 · Friday: Merge sort (Code Crew G5)

Friday: Race the sorts

Mission Control asks which sort the fleet should use for the big catalog.

Rocket and Raven run both sorts on the same lists. Nova keeps a tally of every comparison.

"For 8 cards, selection sort is not so bad," Rocket says. Then the lists get longer.

Raven reads the tallies. "What do you notice as the lists double?"

Nova shows the numbers in big glowing digits. "Here is a hint. Look at how fast each column grows."

We ran both sorts on the same mixed-up lists, with a tally of every comparison.

Selection sort compares each card with almost every other card. Doubling the list makes about four times the work.

Merge sort splits in halves, so it has few levels. Doubling the list makes only two to three times the work.

USE THE TABLE.

For 64 items, which sort made fewer comparisons?

From 32 to 64 items, about how much did selection sort grow?

Selection sort makes the same number of comparisons for every list of 16 items. What is that number?

WHY THIS EXERCISESelection sort always checks every unsorted item, so its tally only depends on the length.

Statement	True or false?
Merge sort uses recursion.	?
Selection sort uses less work for long lists.	?
Both sorts give the same sorted list.	?

WHY THIS EXERCISETwo correct algorithms give the same answer, but one can do far less work.

def selection_comparisons(n):
    return n * (n - 1) // 2

for n in [8, 16, 32, 64, 128]:
    print(n, selection_comparisons(n))

What number prints next to 128?

What number prints next to 8?

How many comparisons does selection sort make for 10 items?

How many comparisons for 4 items?

RACE CHECK

From 64 to 128 items, about how much does selection sort grow?

Which sort would you pick for 10,000 items?

Which sort uses recursion?

Statement	True or false?
selection_comparisons(16) returns 120.	?
Doubling the list doubles selection sort's work.	?
Merge sort made 307 comparisons for 64 items in the table.	?
For 8 items, the two sorts are fairly close.	?

WHY THIS EXERCISESelection sort grows about four times when the list doubles.

How many comparisons does selection sort make for 20 items?

WHY THIS EXERCISE380 halved is 190.

Write a short note to Mission Control. Say which sort the fleet should use and why.

Week 9 complete! You built a sort that splits, sorts and merges, and you measured why it wins. Next week we explore trees.