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

Tuesday

The merge function
// Split, sort, merge
⏱ about 15 min

Tuesday: The merge function

Rocket wants the computer to merge sorted lists for the catalog. He uses two fingers on the screen to track the fronts.

"My fingers are the spot numbers," he says. "One for each list."

Raven watches. "What do you notice about when a finger moves?"

"Only the finger on the card I took moves forward," Rocket says.

Nova hums. "Here is a hint. Use i for one finger and j for the other."

merge in Python

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:]

print(merge([2, 5, 8], [3, 4, 9]))
Output:
[2, 3, 4, 5, 8, 9]
  • i points at the front of left. j points at the front of right.
  • The while loop runs while both lists still have cards. The word and needs both tests to be True.
  • The smaller front card is appended, and only its finger moves forward.
  • left[i:] and right[j:] are the leftovers. One of them is always empty.
  • The + sign joins lists together into one list.
RUN MERGE IN YOUR HEAD.
  • Read the question.
  • Tap your answer.
What does merge([1, 6], [4, 7, 8]) return?
For merge([5], [1, 2, 3]), what are the leftovers?
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])
            ____
    return result + left[i:] + right[j:]

print(merge([2, 5, 8], [3, 4, 9]))
Fill the blank so the right finger moves forward.
WHY THIS EXERCISEWithout moving j, the loop would take the same card from right forever.
What does merge([10, 20], [15]) return? Type the list.
WHY THIS EXERCISEmerge always picks the smaller front, so the result comes out sorted.

Practice lab: three merges

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:]

print(merge([1, 3, 5], [2, 4]))
print(merge([], [7, 8]))
print(merge([6], [6]))
How many items are in the first result?
What does merge([], [7, 8]) return? Type the list.
How many times does the while loop run for merge([], [7, 8])?
In merge([6], [6]), which list gives its 6 first, left or right?
MERGE CODE CHECK
  • Read the question.
  • Tap your answer.
In merge([1, 3, 5], [2, 4]), what are the leftovers?
What does i point at?
What does [1, 2] + [3] make?
StatementTrue or false?
merge returns a sorted list when both inputs are sorted.?
Both i and j move forward on every pass.?
left[i:] is empty when i equals len(left).?
merge works when one list is empty.?
WHY THIS EXERCISEOne finger moves per pass, and the leftovers finish the job.
What does merge([4, 9], [1, 2]) return? Type the list.
WHY THIS EXERCISEThe leftovers 4 and 9 go on the end, already sorted.

Excellent! merge is the heart of merge sort. Tomorrow we learn how to get sorted piles to merge in the first place.

← Monday