Python and Mergesorts- 12 mins
Two 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 pseudo-burgers and every stirfry imaginable, I have decided that the dollars saved on dirt-cheap ground beef is not worth the sanity loss.
My rendition of Frankenstein's monster.
- Part 1: The Basic Mergesort
- Part 2: The Bottom-Up Mergesort
- Part 3: In-Place Mergesort
- Part 4: Complexity Analysis
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 bottom-up 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 straight-forward 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 fixed-length arrays - from what I have read, they are variable-length arrays, which means that I could pass each half as a separate list (
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 position-tracking integers:
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]
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 Bottom-Up Mergesort
Recusion adds overhead that can become important once the input size is very large.
The bottom-up 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: In-Place Mergesort
The premise behind the in-place 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 bottom-up 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 =  * length sort(list, temp, 0, length-1) def bottomup_mergesort(list): length = len(list) temp =  * length size = 1 while size < length: pos = 0 while pos < length: if (pos+2*size-1 >= length): merge(list, temp, pos, pos+size-1, length-1) else: merge(list, temp, pos, pos+size-1, pos+2*size-1) pos+=2*size size+=size return
Part 4: Complexity Analysis
I will get back to this, pretty tired now. Cheers!