Rocket has eight jumbled ID cards. "Merging is great," he says. "But merge needs sorted piles, and my cards are a mess!"
Raven splits the cards into two piles of four, then piles of two, then single cards.
"What do you notice about a pile with just one card?" she asks.
Rocket laughs. "It is already sorted! There is nothing to put in order."
Nova sparkles. "Here is a hint. Single cards are sorted piles. What can you do with sorted piles?"
To split a list in half, find the middle spot with len(items) // 2. Then slice up to it, and from it.
cards = [5, 2, 7, 1, 6, 3, 8, 4] mid = len(cards) // 2 print(cards[:mid]) print(cards[mid:])
Output: [5, 2, 7, 1] [6, 3, 8, 4]
cards[:mid] takes the items before spot mid. cards[mid:] takes spot mid to the end.
| Level | Piles |
|---|---|
| Start | 5 2 7 1 6 3 8 4 |
| Split 1 | 5 2 7 1 | 6 3 8 4 |
| Split 2 | 5 2 | 7 1 | 6 3 | 8 4 |
| Split 3 | 5 | 2 | 7 | 1 | 6 | 3 | 8 | 4 |
| Merge 1 | 2 5 | 1 7 | 3 6 | 4 8 |
| Merge 2 | 1 2 5 7 | 3 4 6 8 |
| Merge 3 | 1 2 3 4 5 6 7 8 |
Eight cards split 3 times to reach single cards. Then 3 levels of merging build them back up, sorted.
cards = [9, 3, 6, 1, 8] mid = len(cards) // 2 print(mid) print(cards[:mid]) print(cards[mid:])
| Statement | True or false? |
|---|---|
| cards[:mid] and cards[mid:] together hold every card. | ? |
| A pile of one card must be sorted again. | ? |
| 16 cards need 4 split levels. | ? |
| The merging goes back up the same number of levels. | ? |
Wonderful! You saw the whole shape of merge sort. Tomorrow we write it with recursion.