Implementing Merge Sort in Python
Merge Sort is an algorithm used to sort lists. It breaks the list down into lists with a length of one and then merges them.
In joining them, each of the arrays is already pre-sorted. So, let’s first learn how to join two pre-sorted arrays.
It helps to think of this outside of the realm of code. Let’s say you have two groups of people, both arranged from shortest to tallest. If you wanted to combine them into one sorted group, how would you do it?
The answer is simpler than you might think. Let’s say the groups are ordered from shortest to tallest, and the new group also needs to be ordered from shortest to tallest.
The shortest person has to be the first person in one of the two lines. If two people are the shortest person in their respective groups, the shorter of the two is the shortest person overall (or it’s a tie).
So, we pull the first person in both of the two lines. We line them up back to back, and then the shorter of the two enters a new group. We then repeat the process, telling the shortest remaining person to get to the end of the new group, where they reign supreme as the tallest person, if only for a moment.
Once we’ve repeated the process enough that one of the groups is empty, there must be one group remaining with people in it. The group with people in it stays in order and gets to the back of the new group.
Just like that, you have your single sorted group. Keep this process in mind when we do it with code.
You have two sorted arrays.
arrA = [0,1,3,4,4,5,7,10,13,14,16,17,18,19,21,24,25,27,28,30];
arrB = [1,2,3,5,7,8,10,11,12,13,15,18,22,22,23,25,28,28,29,29];Then there is the new, single sorted array.
sorted = []The first element of those arrays must be the smallest element. Whichever one is smallest gets removed from its array and joins the new array.
if (arrA[0] < arrB[0]):
sorted.append(arrA[0])
del arrA[0]
else:
sorted.append(arrB[0])
del arrB[0]This process gets repeated until one of the arrays is empty. We can replicate this process with a while loop.
while (len(arrA) and len(arrB)):The process of selecting the first element of each array gets repeated in the loop
while (len(arrA) and len(arrB)):
if (arrA[0] < arrB[0]):
sorted.append(arrA[0])
del arrA[0]
else:
sorted.append(arrB[0])
del arrB[0]This loop will finish executing once one of the groups is empty. To finish the process here we could figure out which array is empty and move everything in that array to the end of the single sorted array.
A simpler solution is to just concatenate ArrA and ArrB to the back of singleSorted. JS will just not append anything with the empty array and the solution will be fine.
return sorted + arrA + arrBNow, we just wrap this in a function and we get a full solution.
def merge(arrA,arrB):
sorted = []
while (len(arrA) and len(arrB)):
if (arrA[0] < arrB[0]):
sorted.append(arrA[0])
del arrA[0]
else:
sorted.append(arrB[0])
del arrB[0]
return sorted + arrA + arrBAnd if we run the function with our two arrays, we get this.
arrA = [0,1,3,4,4,5,7,10,13,14,16,17,18,19,21,24,25,27,28,30];
arrB = [1,2,3,5,7,8,10,11,12,13,15,18,22,22,23,25,28,28,29,29];print(merge(arrA,arrB));/* [0, 1, 1, 2, 3, 3, 4, 4, 5, 5, 7, 7, 8, 10, 10, 11, 12, 13, 13, 14, 15, 16, 17, 18, 18, 19, 21, 22, 22, 23, 24, 25, 25, 27, 28, 28, 28, 29, 29, 30] */
Just in case you didn’t get it, here’s a YouTube video explaining the process. (It’s JavaScript, but the syntax is the only thing you need to c)
So, let’s take the next step. We are going to break the array down into pieces with a length of one, and then join them back together using this algorithm and recursion.

Let’s declare a function that does this.
def mergeSort(arr):The first thing we want to do is check to see if the length of the array is one. Look at the above example. We just return the array if it has a length of one because if there is only one element, it has to be in order.
if (len(arr) <= 1):
return arrIf the array doesn’t have a length of one, we want to split in half and call the same function on each of the newly formed arrays. This process is known as recursion.
pointer = int(len(arr) / 2)
left = mergeSort(arr[0:pointer])
right = mergeSort(arr[pointer:len(arr)])After that, we want to take the two arrays that we get back and merge them into one sorted array. These arrays will come pre-sorted, so we can use the ‘merge’ function that we created above.
return merge(left,right)This is what the final code will look like:
def merge(arrA,arrB):
sorted = []
while (len(arrA) and len(arrB)):
if (arrA[0] < arrB[0]):
sorted.append(arrA[0])
del arrA[0]
else:
sorted.append(arrB[0])
del arrB[0]
return sorted + arrA + arrBdef mergeSort(arr):
if (len(arr) <= 1):
return arr
pointer = int(len(arr) / 2)
left = mergeSort(arr[0:pointer])
right = mergeSort(arr[pointer:len(arr)])
return merge(left,right)
I added some print statements to help visualize the process
[52][26][26, 52][93][17][17, 93][17, 26, 52, 93][77][31][31, 77][44][55][20][20, 55][20, 44, 55][20, 31, 44, 55, 77][17, 20, 26, 31, 44, 52, 55, 77, 93][17, 20, 26, 31, 44, 52, 55, 77, 93]
Every subset is broken in half until it get to a length of one. It then gets merge sorted with another array with a length of one. This new array has a length of two, but it’s sorted, so we can call ‘merge’ on it when joining it to another array.
