Merge Sort

Task: Sort this array in ascending order

def merge_sort(arr):    if len(arr) <= 1:        return arr    mid = len(arr) // 2    left  = merge_sort(arr[:mid])    right = merge_sort(arr[mid:])    return merge(left, right) def merge(a, b):    out = []    while a and b:        if a[0] <= b[0]:            out.append(a.pop(0))        else:            out.append(b.pop(0))    return out + a + b

What you are watching

Merge sort on seven values, drawn as the recursion it is. The array is split in half, each half is split again, and the splitting stops when a piece holds a single value, which is sorted by definition. The pieces then come back up: two sorted runs are merged by comparing their front values and taking the smaller, which is where the ordering is actually created. Nothing sorts on the way down and nothing is compared until the way back up. Each level of the tree walks past every value once, and halving the array down to single values takes log n levels, so the sort costs n log n on every input there is.