Learn Web Development with Python

Single-thread multipart mergesort

The code for the multipart version of the algorithm is quite simple. We can reuse the merge function, but we'll have to rewrite the sort one:

# ms/algo/multi_mergesort.pyfrom functools import reducefrom .mergesort import mergedef sort(v, parts=2):    assert parts > 1, 'Parts need to be at least 2.'    if len(v) <= 1:        return v    chunk_len = max(1, len(v) // parts)    chunks = (        sort(v[k: k + chunk_len], parts=parts)        for k in range(0, len(v), chunk_len)    )    return multi_merge(*chunks)def multi_merge(*v):    return reduce(merge, v)

We saw reduce in Chapter 4, Functions, the Building Blocks of Code, when we coded our own factorial function. The way it works within multi_merge is to merge the first two lists in v. Then the result ...