Merge Sort: A Faster Sorting Algorithm

There are several well-known, fast sorting algorithms; merge sort, quick sort, and heap sort are the ones you are most likely to encounter in a future computer science course. Most of them involve techniques that you haven’t learned yet, but merge sort can be written in a more accessible way. Merge sort is built around the idea that taking two sorted lists and merging them is proportional to the number of items in both lists. The running time for merge sort is N log₂N.

Start with tiny lists and keep merging them until you have a single sorted list.

Merging Two Sorted Lists

Given two sorted lists L1 and L2, you can produce a new sorted list by iterating through L1 and L2 and comparing pairs of elements. (You’ll see how to make these two sorted lists in a bit.)

Here is the code for merge:

​	​def​ ​merge​(L1: list, L2: list) -> list:
​	​"""Merge sorted lists L1 and L2 into a new list and return that new list.​
​
​	​ >>> merge([1, 3, 4, 6], [1, 2, 5, 7])​
​	​ [1, 1, 2, 3, 4, 5, 6, 7]​
​	​ """​
​
​	newL = []
​	i1 = 0
​	i2 = 0
​
​	​# For each pair of items L1[i1] and L2[i2], copy the smaller into newL.​
​	​while​ i1 != len(L1) ​and​ i2 != len(L2):
​	​if​ L1[i1] <= L2[i2]:
​	newL.append(L1[i1])
​	i1 += 1
​	​else​:
​	newL.append(L2[i2])
​	i2 += 1
​
​	​# Gather any leftover items from the two sections.​
​	​# Note that one of them will be empty because of the loop condition.​
​	newL.extend(L1[i1:])
​	newL.extend(L2[i2:])
​	​return​ newL

i1 and i2 are the indices into L1 and L2, respectively; in each iteration, compare L1[i1] to L2[i2] and copy the smaller item to the resulting list. At the end of the loop, you have run out of items in one of the two lists, and the two extend calls will append the rest of the items to the result.

Merge Sort

Here is the header for mergesort:

​	​def​ ​mergesort​(L: list) -> None:
​	​"""Reorder the items in L from smallest to largest.​
​
​	​ >>> L = [3, 4, 7, -1, 2, 5]​
​	​ >>> mergesort(L)​
​	​ >>> L​
​	​ [-1, 2, 3, 4, 5, 7]​
​	​ """​

The mergesort function uses the merge operation to perform 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 = []
​	​for​ i ​in​ range(len(L)):
​	workspace.append([L[i]])

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

Instead, 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:

Here is your refined algorithm:

• Take list L and make a list of one-item lists from it.
• Start index i off at 0.
• 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, you can go straight to code:

​	​def​ ​mergesort​(L: list) -> None:
​	​"""Reorder the items in L from smallest to largest.​
​
​	​ >>> L = [3, 4, 7, -1, 2, 5]​
​	​ >>> mergesort(L)​
​	​ >>> L​
​	​ [-1, 2, 3, 4, 5, 7]​
​	​ """​
​
​	​# Make a list of 1-item lists so that we can start merging.​
​	workspace = []
​	​for​ i ​in​ range(len(L)):
​	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:
​	L[:] = workspace[-1][:]

Notice that since you’re constantly making new lists, you need to copy the last of the merged lists back into the parameter L.

Merge Sort Analysis

Merge sort’s performance turns out to be N log₂N, where N is the number of items in L. The following diagram illustrates how the one-item lists are merged into two-item lists, then four-item lists, and so on, until a single N-item list is formed:

The first part of the function, which creates a list of one-item lists, takes N iterations, one for each item.

The second loop, where you continually merge lists, requires careful analysis. Start with the last iteration, in which you merge two lists with approximately N/2 items. As you’ve seen, the function merge copies each element into its result exactly once, so with these two lists, this merge step takes roughly N steps.

In the previous iteration, there were four lists of size N/4 to be merged into two lists of size N/2. Each of these two merges takes roughly N/2 steps, so the two merges together take roughly N steps total.

In the iteration before that, there were a total of eight lists of size N/8 to merge into the four lists of size N/4. Four merges of this size together also take roughly N steps.

You can subdivide a list with N items a total of log₂ N times using an analysis similar to the one used for binary search. Since at each “level” there are a total of N items to be merged, each of these log₂ N levels takes roughly N steps. Hence, merge sort takes time proportional to N log₂ N.

That’s an awful lot of code to sort a list! There are shorter and clearer versions but, again, they rely on techniques that hasn’t been yet introduced.

Despite the extensive code and the somewhat messy approach (which creates a numerous sublists), merge sort proves to be significantly faster than selection sort and insertion sort. More importantly, it grows at the same rate as the built-in sort (all times in ms):

List Length	Selection Sort	Insertion Sort	Merge Sort	list.sort
1000	29	14	1.5	0.1
2000	117	58	3.1	0.2
3000	265	135	4.5	0.3
4000	466	237	6.2	0.4
5000	732	370	8.1	0.5
10000	3001	1494	17.9	1.2

Отправить