## Mergesort

Here is the header for mergesort:

def mergesort(L):

"""Sort L in increasing order.""" Figure 11.8: List of lists in mergesort

Mergesort uses function merge to do the bulk of the work. Here is the algorithm, which creates and keeps track of a list of lists:

• Take list L, and make a list of one-item lists from it.

• As long as there are two lists left to merge, merge them, and append the new list to the list of lists.

The first step is straightforward:

# Make a list of 1-item lists so that we can start merging.

workspace.append([L[i]])

The second step is trickier. If we remove the two lists, then we'll run into the same problem that we ran into in binsort: all the following lists will need to shift over, which takes time proportional to the number of lists.

Instead, we'll keep track of the index of the next two lists to merge. Initially, they will be at indices 0 and 1, and then 2 and 3, and so on (Figure 11.9, on page 233). Here's our refined algorithm:

• Take list L, and make a list of one-item lists from it.

• As long as there are two lists, at indices i and i + 1, merge them, append the new list to the list of lists, and increment i by 2.

With that, we can go straight to code:

# Make a list of 1-item lists so that we can start merging, workspace = []

workspace.append([L[i]])

# The next two lists to merge are workspace[i] and workspace[i + 1], i = 0

# As long as there are at least two more lists to merge, merge them, while i < len(workspace) - 1:

L1 = workspace[i] L2 = workspace[i + 1] newL = merge(L1, L2) workspace.append(newL) i += 2

# Copy the result back into L. if len(workspace) != 0:

Notice that, since we're always making new lists, we need to copy the last of the merged lists back into parameter L.