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

Thursday

Merge sort in Python
// Split, sort, merge
⏱ about 15 min

Thursday: Merge sort in Python

Rocket wants to turn the split and merge table into code. "Do I need a loop for each level?" he wonders.

Raven draws a box around one half of the cards. "What do you notice about sorting this half?"

"It is the same job as sorting the whole thing, just smaller!" Rocket says.

"Like the nesting boxes," Raven says.

Nova glows. "Here is a hint. Base case, smaller step. You know this pattern."

The merge_sort function

This version prints each merge so we can watch it work. It uses the merge function from Tuesday.

def merge(left, right):
    result = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i = i + 1
        else:
            result.append(right[j])
            j = j + 1
    return result + left[i:] + right[j:]

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    print("merging", left, right)
    return merge(left, right)

print(merge_sort([5, 2, 7, 1]))
Output:
merging [5] [2]
merging [7] [1]
merging [2, 5] [1, 7]
[1, 2, 5, 7]
  • Base case: a list of 0 or 1 items is already sorted, so return it.
  • Smaller steps: sort the left half and the right half with merge_sort.
  • Then merge the two sorted halves and return the result.
TAP THE MERGES OF MERGE_SORT([4, 3, 2, 1]) INTO THE ORDER THEY PRINT.
  • Tap a card.
  • Then tap its spot.
11st
22nd
33rd
Statement about merge_sortTrue or false?
The base case is a list with 0 or 1 items.?
merge_sort calls itself twice in each call that is not a base case.?
The right half is merged before the left half is sorted.?
WHY THIS EXERCISEEach call waits for both halves to come back sorted before it merges.
How many merging lines would merge_sort print for a list of 8 items?
WHY THIS EXERCISEEvery merge joins two piles into one, so 8 single cards need 7 merges to become one pile.

Practice lab: sort three cards

def merge(left, right):
    result = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i = i + 1
        else:
            result.append(right[j])
            j = j + 1
    return result + left[i:] + right[j:]

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    print("merging", left, right)
    return merge(left, right)

print(merge_sort([3, 1, 2]))
How many merging lines print?
What is the first item of the final list?
How many merging lines for a list of 4 items?
How many merging lines for a list of 16 items?
MERGE_SORT CHECK
  • Read the question.
  • Tap your answer.
What is the first merging line for [3, 1, 2]?
What is the base case of merge_sort?
What does merge_sort([]) return?
StatementTrue or false?
merge_sort([3]) prints nothing.?
merge_sort([3, 1, 2]) prints merging [3] [1, 2] first.?
merge_sort uses merge to join the halves.?
Each half is sorted before the merge.?
WHY THIS EXERCISEEach call waits for its halves, then merges them.
How many merging lines would merge_sort print for a list of 5 items?
WHY THIS EXERCISEFive single cards need four merges to become one pile.

Fantastic! You read a recursive sort. That is real computer science. Tomorrow we race it against selection sort.

← Wednesday