Python and Mergesorts
 12 minsTwo weeks into my second year of university, I have learned a very important lesson:
Ground beef is not something I want to eat every day.
Not too long ago, eggs and ground beef was the holy binity (is that a word?) of my daily diet, but after half a summer of ground beef in fried rice, pasta sauce, messy pseudoburgers and every stirfry imaginable, I have decided that the dollars saved on dirtcheap ground beef is not worth the sanity loss.
My rendition of Frankenstein's monster.
 Prelude
 Part 1: The Basic Mergesort
 Part 2: The BottomUp Mergesort
 Part 3: InPlace Mergesort
 Part 4: Complexity Analysis
Prelude
Towards the end of summer, with nothing to distract me from pickle sales except a few personal projects, I decided to start a Coursera course in algorithms.
It was fantastic, very confusing, and definitely made me feel very cool. I got up to Week 3 before school started. Unfortunately, I have come to accept that I probably won’t get the chance to finish the course any time soon.
The lectures use Java as an expository language. Having spent a lot of time with Java already, I think I am long overdue for some Python experience  especially because I have a big club project coming up that will use a lot of Python. So here goes a very brief walkthrough of what I’ve learnt about mergesorts, explained in Python.
I’ll be implementing a basic mergesort and demonstrating a nifty alternative to it: the bottomup mergesort.
Hopefully, this might be useful to someone one day, and my existence will have some purpose. If you are interested in learning this content properly I highly recommend the Coursera course.
Part 1: The Basic Mergesort
When sorting a list, the basic idea behind a mergesort goes as follows:
 Divide the items in half
 Recursively sort each half
 Merge the sorted halves
 Tada! Feast on your your sorted list/array/whatever.
This is fairly straightforward to implement. To start off, I need something that can merge two sorted halves of a list, to solve Step 3.
Merging sorted halves
Python arrays aren’t like Java’s fixedlength arrays  from what I have read, they are variablelength arrays, which means that I could pass each half as a separate list (left
and right
) and append()
elements in order onto a result
. This would alleviate the need for a copy of the list in temp
. It also means that, at the expense of some extra memory usage, the algorithm will be able to complete a merge with less data movement and should be faster overall.
For this post, I will go with Method 2, but I will include an implementation of Method 1 at the end. Using Method 2, the core of my merge
will be a loop that iterates two positiontracking integers:

x
overleft

y
overright
This allows the algorithm to compare the elements of each half to one another to sort them.
elif right[y] < left[x]:
result.append(right[y])
y+=1
else:
result.append(left[x])
x+=1
This works, but can be optimized a bit  if we reach the end of the first half, we know that the remaining items in the second half are all larger, so we can just add the next value straight away (and vice versa).
The complete implementation actually took me a while to get right because I’m bad at Python, but the resulting merge()
looks like this:
def merge(left, right):
result = []
x, y = 0, 0
for z in range(0, len(left) + len(right)):
if x == len(left): # if at the end of 1st half,
result.append(right[y]) # add all values of 2nd half
y+=1
elif y == len(right): # if at the end of 2nd half,
result.append(left[x]) # add all values of 1st half
x+=1
elif right[y] < left[x]:
result.append(right[y])
y+=1
else:
result.append(left[x])
x+=1
return result
And a quick test to verify it works:
left = [5,6,7,8]
right = [1,2,3,4]
print(merge(left,right)) # output = [1, 2, 3, 4, 5, 6, 7, 8]
Yay!
Sorting
Using only merge()
, we can sort an entire list simply by recursively dividing the list into smaller and smaller halves until they can no longer be divided. It is most easily visualized as a tree, where each branch is a smaller and smaller part of the original list.
To do this we need a function, sort()
, that calculates a mid
and calls itself on list[:mid]
(the first half) and list[mid:]
(the second half). By using merge()
on the halves, you eventually end up with a sorted list.
def mergesort(list):
if len(list) < 2: # stop recursion when
return list # sublists are size 1 or 0
mid = int (len(list)/2) # calculate midpoint
left = mergesort(list[:mid]) # recursive sort 1st half
right = mergesort(list[mid:]) # recursive sort 2nd half
return merge(left, right) # merge the two halves
Running a similar test from before verifies that this works:
list = [2,5,1,8,3,8,0]
print(mergesort(list)) # output = [0, 1, 2, 3, 5, 8, 8]
Part 2: The BottomUp Mergesort
Recusion adds overhead that can become important once the input size is very large.
The bottomup mergesort solves this by doing the opposite of the standard mergesort: instead of starting with the entire list and recursively breaking it down, it starts with sublists of size 1 and merges them in pairs until the entire list is sorted.
The process is as follows:
 Break the list into sublists of size 2, and merge the two halves of each sublist. This the halves are of size 1, this completely sorts each sublist.
 Break the list into sublists twice as large, where each half has been sorted by Step 1. This means each sublist can be merged and sorted.
 Repeat step 2 until the sublist is the size of the entire list, by which point the entire list has been sorted.
The implementation, using the same merge()
from part one:
def bottomup_mergesort(list):
length = len(list)
size = 1
while size < length:
size+=size # initializes at 2 as described
for pos in range(0, length, size):
sublist_start = pos
sublist_mid = pos + (size / 2)
sublist_end = pos + size
left = list[ sublist_start : sublist_mid ]
right = list[ sublist_mid : sublist_end ]
list[sublist_start:sublist_end] = merge(left, right)
return list
And a test to verify it works:
randlist = []
for x in range (0, 100001):
randlist.append(random.randint(0, 100))
list = bottomup_mergesort(randlist)
if sorted(l) == l:
print("Is sorted!") # prints!
Part 3: InPlace Mergesort
The premise behind the inplace mergesort is that by using an auxillary array, temp
, and operating on the original list
, the algorithm will not need to take up extra memory by passing around subarrays.
I won’t go too much into the details, but here are my implementations of both a normal mergesort and a bottomup mergesort, based on the algorithm implemented in the Coursera course:
def merge(list, temp, low, mid, high):
'''
Merges two sorted halves of a list in order.
'''
for z in range(low, high+1):
temp[z] = list[z] # copy items into temp
first = low # position in 1st half
sec = mid + 1 # position in 2nd half
for z in range(low, high+1):
if first > mid: # if past the end of 1st half,
list[z] = temp[sec] # add next value of 2nd half
sec+=1
elif sec > high: # if past the end of 2nd half,
list[z] = temp[first] # add value from 1st half,
first+=1
elif temp[sec] < temp[first]: # if value in 2nd < value in 1st,
list[z] = temp[sec] # add value from 2nd half,
sec+=1
else: # if value in 1st < value in 2nd,
list[z] = temp[first] # add next value in 1st half,
first+=1 # imcrement first
def sort(list, temp, low, high):
if high <= low:
return # stop recursion
mid = low + (high  low) / 2 # calculate mid between high and low
sort(list, temp, low, mid) # recursive sort the first half
sort(list, temp, mid+1, high) # recursive sort the second half
merge(list, temp, low, mid, high) # merge the two halves
def mergesort(list):
length = len(list)
temp = [0] * length
sort(list, temp, 0, length1)
def bottomup_mergesort(list):
length = len(list)
temp = [0] * length
size = 1
while size < length:
pos = 0
while pos < length:
if (pos+2*size1 >= length):
merge(list, temp, pos, pos+size1, length1)
else:
merge(list, temp, pos, pos+size1, pos+2*size1)
pos+=2*size
size+=size
return
Part 4: Complexity Analysis
I will get back to this, pretty tired now. Cheers!