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

Monday

Merging two sorted piles
// Split, sort, merge
⏱ about 15 min

Monday: Merging two sorted piles

Two survey ships come home. Each one has sorted its own star IDs. Ship A has 2, 5, 8. Ship B has 3, 4, 9.

"I will dump them together and sort all six again," Rocket says.

Raven holds up both piles. "What do you notice? Each pile is already sorted."

"So the smallest card must be on top of one of the piles," Rocket says slowly.

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

Merge by comparing the fronts

  1. Look at the front card of each pile.
  2. Take the smaller one and put it at the end of the new row.
  3. Repeat until one pile is empty.
  4. Put the leftovers from the other pile at the end. They are already sorted.
Pile APile BCompareTakeNew row
2, 5, 83, 4, 92 or 322
5, 83, 4, 95 or 332, 3
5, 84, 95 or 442, 3, 4
5, 895 or 952, 3, 4, 5
898 or 982, 3, 4, 5, 8
(empty)9leftovers92, 3, 4, 5, 8, 9

Six cards were merged with only 5 comparisons. We never had to look past the front of a pile.

MERGE 1, 6 WITH 4, 7, 8. TAP THE CARDS IN THE ORDER YOU TAKE THEM.
  • Tap a card.
  • Then tap its spot.
11st
22nd
33rd
44th
55th
Merging 1, 6 with 4, 7, 8: pile A empties first. Which cards are left over in pile B?
How many comparisons does that merge need?
Statement about mergingTrue or false?
Merging only works if both piles are already sorted.?
You must look at every card in both piles before taking one.?
The leftovers need to be sorted again.?
WHY THIS EXERCISEBecause each pile is sorted, the two fronts are the only cards that could be smallest.

Practice lab: merge by hand

Merge pile A, holding 3, 6, 7, with pile B, holding 1, 5, 8. Only compare the two front cards.

Which card do you take first?
Which card do you take second?
How many comparisons does the whole merge need?
Which card is the leftover at the end?
MERGE CHECK
  • Read the question.
  • Tap your answer.
Merge 2, 9 with 4, 5, 6. Which pile empties first?
What is the leftover card in that merge?
Merge the pile 1 with the pile 2. How many comparisons?
StatementTrue or false?
The first card taken is always the smallest of all.?
Merging 3 cards with 3 cards can take 10 comparisons.?
When one pile is empty, the merge is almost done.?
You only ever compare the two front cards.?
WHY THIS EXERCISEMerging is fast because it never looks past the fronts.
How many comparisons does it take to merge 2, 9 with 4, 5, 6?
WHY THIS EXERCISEAfter 4 comparisons, pile B is empty and 9 goes on the end.

Great merging! Tomorrow we write merge as a Python function.