Mergesort in Action

Assume that we want to sort the array [8, 4, 3, 7, 6, 1, 2, 5]. Note that this is not the type of array whose two halves are already sorted. In fact, it’s a complete mess.

Step 1: First, we make copies of the two halves of the array:

copying the two halves of the original array into two smaller array copies

Step 2: We recursively perform Mergesort on the left copy. In code, this would be written as mergesort([8, 4, 3, 7]). This, in turn, will make copies of the two halves of [8, 4, 3, 7]:

making half-copies of the 8, 4, 3, 7 array

Step 3: We recursively perform Mergesort on the left copy (which I’ll call left half going forward). This means we call mergesort([8, 4]), and thereby create two new subarrays, [8] and [4]:

Step 4: We recursively Mergesort (yes, I’m making it a verb now) the [8]. Since it’s the base case of an array of size 1, we don’t do anything else within this call, and mergesort([8]) is completed.

The reason why a single-element array is the base case is because a single element is, by definition, sorted! (After all, it’s certainly not unsorted, right?) As such, we mark the [8] as sorted:

Step 5: We now Mergesort the right half of [8, 4] by calling mergesort([4]). The [4], too, is an array of size 1, so it is considered sorted:

Step 6: With mergesort([8]) and mergesort([4]) complete, we now proceed to the next step of the mergesort([8, 4]) call, which is to merge the two halves:

Note that the 4 and 8 are now sorted relative to each other.

Step 7: We’ve completed mergesort([8, 4]), which brings us back to call mergesort([8, 4, 3, 7]). We’ve already Mergesorted the left half, so now we Mergesort the right half and call mergesort([3, 7]):

Now, you and I both know that [3, 7] is already sorted, but the computer doesn’t know that yet since it doesn’t have eyeballs.

Step 8: We Mergesort the left half of [3, 7] by calling mergesort([3]). This is a base case, so the [3] is now sorted:

Step 9: We then Mergesort the right half of [3, 7] by calling mergesort([7]). This, too, is a base case, so mergesort([7]) is complete:

Step 10: Now that mergesort([3, 7]) has Mergesorted both its left and right halves, we now merge the halves together:

Step 11: This is where things get exciting. We’re back within the call of mergesort([8, 4, 3, 7]). We’ve already Mergesorted its left half. And we’ve already Mergesorted its right half. This means we get to merge the two halves together. Boom!

The [3, 4, 7, 8] is now sorted.

Step 12: We’ve completed Mergesorting the left half of our original array [8, 4, 3, 7, 6, 1, 2, 5]. Now, it’s time to Mergesort the right half, [6, 1, 2, 5]:

Step 13: We Mergesort the left half of [6, 1, 2, 5] by calling mergesort([6, 1]):

Step 14: We Mergesort the left half of [6, 1], calling mergesort([6]). This is a base case, so the call ends abruptly:

Step 15: We Mergesort the right half of [6, 1] by calling mergesort([1]):

Step 16: We’re done sorting the two halves of [6, 1], so we now merge them:

Step 17: We’re back to mergesort([6, 1, 2, 5]). Since we completed Mergesorting its left half, we now proceed to Mergesort its right half with mergesort([2, 5]):

Step 18: We Mergesort [2]:

Step 19: We Mergesort [5]:

Step 20: We merge the two halves together:

Step 21: We’re back at mergesort([6, 1, 2, 5]). We’ve Mergesorted both halves, so we now merge the two halves together. Boom!

Step 22: Okay, we’re at the climax now. We’re back at our original call of mergesort([8, 4, 3, 7, 6, 1, 2, 5]). We’ve Mergesorted both halves of the array. You know what this means, right?

the final merge back into the original array

BOOM! Our original array is now completely sorted.

Code Implementation: Mergesort

Here’s the code for Mergesort. It’s surprisingly concise:

	def mergesort(array):
	if len(array) <= 1: return

	midpoint = len(array) // 2
	copy_of_left_half = array[:midpoint]
	copy_of_right_half = array[midpoint:]

	mergesort(copy_of_left_half)
	mergesort(copy_of_right_half)
	merge(copy_of_left_half, copy_of_right_half, array)

First, the call simply ends abruptly if the size of the array is 1 or lower. Again, this is the base case.

Next, we make copies of the left and right halves. After that, we Mergesort the left half, and after that, we Mergesort the right half. Finally, we merge the two halves using our merge function from earlier in this chapter.

And that’s it!