Python Sorting Algorithms: merge_sort()
Continuing my series on python sorting algorithms today I’m going to look at Merge Sort. Merge sort is a divide, and conquer strategy where it breaks down your list into halves repeatedly until it has just one element, and reconstructs the list in order. It even uses my favorite recursion method.
The nice thing about recursions is that I can set up my function once, and call on it to execute the cutting in halves of the list I’m sorting. So first let me set up that function. I’ll want to find the middle index of my array so a simple len(items) // 2 should do it. From there I can split my list into a left half, and a right half. Like so…
def merge_sort(items): if len(items) <= 1:
return items middle_index = len(items) // 2
left_split = items[:middle_index]
right_split = items[middle_index:]
Don’t forget a recursion will need a base case to pop out of the loop. The if statement above will ensure that once the list reaches a length of 1 it will stop, and return the items. Otherwise this will half my list over and over again until the length is ≤= 1;
So we broke down the array, what will merge them back together? We’ll need a second function for that. The merge function. I’ll feed into my new function two parameters. The left_split, and the right_split. My merge function will have a new variable -an empty list where the ordered list will be assembled. I’ll name it result.
I’ll use a while loop that’ll run as long as BOTH left_split, and right_split have an element (sometimes our lists are uneven when divided by 2 hence the ‘and’). I’ll use an if/else to compare the left_split and right_split appending the smaller value to the result list. I’ll then pop() that value out of left_split/right_split so the while loop won’t run forever.
And again since our left_split/right_split could be of uneven lengths I’ll add if statements to add any stragglers to the result list, which would also happen to be the biggest value.
I’ll run this new function inside of merge_sort as it breaks down the list, but merge will rebuild it. I’ll then return the rebuilt values.
Here’s how it’ll look. I recommend looking it over a few times, as there are multiple moving pieces in all this. There is a recursion performing a stack (which we can’t see), and a while loop running an operation on the single elements in a list as it climbs out of the recursion.
Kinda confusing, but I hope this helped break it down some for you. I both like the simplicity (recursion), and the combination of an iteration (while loop) to do the work of all this. It has a rain man-esque feel to it that I think is pretty cool.