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.py
from functools import reduce
from .mergesort import merge

def 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 is merged with the third one, after which the result is merged with the fourth one, and so on.

Take a look at the new version of sort. It takes the v list, and the number of parts we want to split it into. The first thing we do is check that we passed a correct number for parts, which needs to be at least two. Then, like before, we have the base of the recursion. And finally we get into the main logic of the function, which is simply a multipart version of the one we saw in the previous example. We calculate the length of each chunk using the max function, just in case there are fewer elements in the list than parts. And then we write a generator expression that calls sort recursively on each chunk. Finally, we merge all the results by calling multi_merge.

I am aware that in explaining this code, I haven't been as exhaustive as I usually am, and I'm afraid it is on purpose. The example that comes after the mergesort will be much more complex, so I would like to encourage you to really try to understand the previous two snippets as thoroughly as you can.

Now, let's take this example to the next step: multithreading.