Learn to build your own merge sort in Python!

Merge Sort: Python

Let's update our `merge_sort()` function so that it returns a sorted list finally!

Finishing the Sort

Our `merge_sort()` function so far only separates the input list into many different parts &mdash; pretty much the opposite of what you'd expect a merge sort to do. To actually perform the merging, we're going to define a helper function that joins the data together.

Creating the Merge Function

How do we break up the data in a merge sort? We split it in half until there's no more data to split. Our first step is to break down all of the items of the list into their own list.

Partitions

Since we've only technically depleted one of our two inputs to `merge()`, we want to add in the rest of the values to finish off our `merge()` function and return the sorted list.

Finishing the Merge

We've written our merge sort! The whole sort takes up two functions: 

`merge_sort()` which is called recursively breaks down an input list to smaller, more manageable pieces.
`merge()` which is a helper function built to help combine those broken-down lists into ordered combination lists.

`merge_sort()` continues to break down an input list until it only has one element and then it joins that with other single element lists to create sorted 2-element lists. Then it combines 2-element sorted lists into 4-element sorted lists. It continues that way until all the items of the lists are sorted!

Only one thing left to do, test it out!

Testing the Sort

What is sorted by a sort? A sort takes in a list of some data. The data can be words that we want to sort in dictionary order, or people we want to sort by birth date, or really anything else that has an order. For the simplicity of this lesson, we're going to imagine the data as just numbers.

The first step in a merge sort is to separate the data into smaller lists. Then we break those lists into even smaller lists. Then, when those lists are all single-element lists, something amazing happens! Well, kind of amazing. Well, you might have expected it, we do call it a "merge sort". We merge the lists.

Separation

Now we need to build out our result list. When we're merging our lists together, we're creating ordered lists that combine the elements of two lists.