Not the whole exercise: just the merge, on two sorted lists you are handed. Two positions walk along the lists, and each step takes the smaller front value.
left, right = [1, 4, 9], [2, 3, 10, 12]
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
merged += left[i:] + right[j:] # whatever is left over
print(merged) # -> [1, 2, 3, 4, 9, 10, 12]
- One comparison per value
Each step moves one value into merged, so merging costs no more than the two lists' combined length. That is why merge sort is fast.
- The leftovers are already in order
When one list runs out, the rest of the other is sorted and larger than everything taken so far. Forgetting that last line quietly drops values.
- <= keeps equal values in their original order
Taking from the left on a tie means values that compare equal keep the order they arrived in. That property is called stable, and Python’s own sort promises it.
A list of 0 or 1 items is sorted: return a copy. Anything longer: split it at the middle, sort each half with merge_sort, and merge the two results.
mid = len(items) // 2. left = merge_sort(items[:mid]); right = merge_sort(items[mid:]). Then merge them the way the Study example does, including the leftovers.
Base case: if len(items) <= 1, return items[:]. Merge: walk i along left and j along right, append the smaller each time (take left on a tie), then add left[i:] and right[j:].
def merge_sort(items): if len(items) <= ____: return items[:] mid = len(items) // 2 left, right = merge_sort(items[:mid]), merge_sort(items[____:]) merged, i, j = [], 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: merged.append(left[i]); i += 1 else: merged.append(right[j]); j += 1 return merged + left[i:] + ____
def merge_sort(items):
if len(items) <= 1:
return items[:]
mid = len(items) // 2
left = merge_sort(items[:mid])
right = merge_sort(items[mid:])
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
return merged + left[i:] + right[j:]
Splitting a one-item list gives an empty half and a one-item half, and the one-item half splits the same way again, forever. One item has to be where it stops.
The contract asks for a new list. Returning items itself would hand the caller back their own list for inputs of length 0 or 1, and a change to one would show in the other.
The list is halved about log2(n) times, and each level of merging touches every value once. A million values take about twenty levels, where comparing every pair would take half a trillion comparisons.
Always use sorted() in real code. Python’s sort is a merge sort refined over twenty years, written in C, and much faster than anything written in Python. Write merge sort to understand divide and conquer, and because the merge step on its own is useful whenever you have two sorted lists to combine.
- Add a key argument so merge_sort(words, key=len) sorts by length, keeping the sort stable.
- Count the inversions in a list, pairs that are the wrong way round, during the merge.
- Write a version that sorts a list in place and compare how much memory each uses.