← Back to course
Code Crew G5 / Week 09 / Crew Quest
6/6
Week 09 · Merge sort

Crew Quest

Crew Quest: Split and merge
// Split, sort, merge
⏱ about 15 min

Crew Quest: Split and merge

The whole family is invited to the observation deck for a card race.

Rocket deals eight numbered cards to Raven, who splits them into two piles and hands one back.

"Sort your half, I will sort mine," Raven says. "What do you notice about our two piles at the end?"

"They are both sorted! Now we just merge them," Rocket says.

Nova twirls. "Here is a hint. Only ever compare the two top cards."

  1. Merge joins two sorted lists by always taking the smaller front item.
  2. Leftovers go on the end with no more comparisons.
  3. Merge sort splits a list in halves until each part has one item.
  4. One item is already sorted. That is the base case.
  5. For long lists, merge sort makes far fewer comparisons than selection sort.
◇ SPLIT AND MERGE
Write the numbers 1 to 8 on eight paper cards. Shuffle them.
Split them into two piles of four. Each person takes one pile.
Split your pile into twos, then single cards. Merge them back up, sorted.
Now merge your two sorted piles of four together, comparing only top cards.
Check that the final row goes 1 to 8.
For a grown-up
Splitting the work between two people is a nice way to see why merge sort is fast. Each half can be sorted at the same time.
RECAP QUESTION
  • Read the question.
  • Tap your answer.
Two sorted piles: 3, 7 and 5, 6. Which card do you take first?
Bonus recap statementTrue or false?
Merge only works on sorted piles.?
Leftovers must be sorted again.?
merge_sort splits until each pile has one card.?
n cards need n - 1 merges.?
WHY THIS EXERCISESplit, then merge, is the whole idea of merge sort.
How many split levels for 8 cards?
How many merges for 8 cards?
Merging 1, 4 with 2, 3: which card comes second?

Quest complete! Next week we explore the fleet command tree.

← Friday