Learn Web Development with Python

Single-thread mergesort

Let's see how all this translates into code, starting by learning how to code our own homemade mergesort:

# ms/algo/mergesort.pydef sort(v):    if len(v) <= 1:        return v    mid = len(v) // 2    v1, v2 = sort(v[:mid]), sort(v[mid:])    return merge(v1, v2)def merge(v1, v2):    v = []    h = k = 0    len_v1, len_v2 = len(v1), len(v2)    while h < len_v1 or k < len_v2:        if k == len_v2 or (h < len_v1 and v1[h] < v2[k]):            v.append(v1[h])            h += 1        else:            v.append(v2[k])            k += 1    return v

Let's start from the sort function. First we encounter the base of the recursion, which says that if the list has 0 or 1 elements, we don't need to sort it, we can simply return it as it is. If that is not the case, then we calculate the midpoint (mid), and recursively ...