This Merge Sort lesson is for a beginner. Read the short notes, run each example, then change one name or number and run it again.
Merge sort splits the list in half, sorts each half, and merges the two sorted halves.
It needs extra space for the merge and it stays predictable on already messy data.
Example 1: Start here
The <= test keeps equal values in their original order.
def merge_sort(items): # define the function; it runs when you call it
if len(items) < 2: # run the indented lines only when this is true
return items # send this value back to the caller
mid = len(items) // 2 # how many items
left = merge_sort(items[:mid]) # the value at this position
right = merge_sort(items[mid:]) # the value at this position
out = [] # a list; the values stay in this order
i = j = 0 # both names get the same value
while i < len(left) and j < len(right): # keep repeating while this stays true
if left[i] <= right[j]: # run the indented lines only when this is true
out.append(left[i]) # add one item at the end of the list
i += 1 # update the stored value
else: # runs when the test above was false
out.append(right[j]) # add one item at the end of the list
j += 1 # update the stored value
return out + left[i:] + right[j:] # send this value back to the caller
print(merge_sort([4, 1, 3, 2]))
Example 2: Walk the values
Merge Sort starts by visiting one value at a time. Read the printed lines from top to bottom.
values = [13, 3, 11, 7] # a list; the values stay in this order
for value in values: # repeat the indented lines once per value
print(value)
Example 3: Keep the largest
Many data-structure lessons reduce a list to one answer. This one remembers the largest number seen so far.
values = [13, 3, 11, 7] # a list; the values stay in this order
best = values[0] # the first value
for value in values: # repeat the indented lines once per value
if value > best: # run the indented lines only when this is true
best = value # another name for the same value
print(best)
Example 4: Search for a target
A search asks one yes-or-no question: is the target in the collection? Merge Sort builds on that question.
values = [3, 13, 11] # a list; the values stay in this order
target = 13 # a whole number
print(target in values) # in is True when the value is found
The <= test keeps equal values in their original order.
