Bummer! This is just a preview. You need to be signed in with a Basic account to view the entire video.
Start a free Basic trial
to watch this video
Before we implement merge sort in code lets understand how it works conceptually.
Resources

0:00
[MUSIC]

0:04
Now that we've seen two different data structures, let's circle back and

0:08
apply what we know about algorithms to these new concepts.

0:11
One of the first algorithms you learned about was binary search.

0:14
And we learned that with binary search there was one precondition.

0:18
The data collection needs to be sorted.

0:20
Over the next few videos let's implement the merge sort algorithm,

0:23
which is one of many sorting algorithms on both arrays or Python lists and

0:28
the singly linked list we just created.

0:30
This way we can learn a new sorting algorithm that has real world use cases

0:35
and see how a single algorithm can be implemented on different data structures.

0:40
Before we get into code, let's take a look at how merge sort works conceptually,

0:45
and we'll use an array to work through this.

0:48
We start with an unsorted array of integers, and

0:51
our goal is to end up with an array sorted in ascending order.

0:55
Merge Sort works like binary sort by splitting up the problem into

0:59
subproblems, but it takes the process one step further.

1:03
On the first pass, we're going to split the array into two smaller arrays.

1:07
Now in binary search, one of these subarrays would be discarded.

1:11
But that's not what happens here.

1:12
On the second pass, we're going to split each of those subarrays into further,

1:17
smaller, evenly sized arrays.

1:19
And we're going to keep doing this until we're down to single element arrays.

1:23
After that, the Merge Sort algorithm works backwards,

1:27
repeatedly merging the single element arrays, and sorting them at the same time.

1:32
Since we start at the bottom, by merging two single element arrays,

1:37
we only need to make a single comparison to sort the resulting merged array.

1:42
By starting with smaller arrays that are sorted as they grow, Merge Sort has

1:47
to execute fewer sort operations than if it sorted the entire array at once.

1:52
Solving a problem like this by recursively breaking down the problem into

1:56
subparts until it is easily solved is an algorithmic strategy known as divide and

2:01
conquer.

2:02
But instead of talking about all of this in the abstract, let's dive into the code.

2:06
This way, we can analyze the run time as we implement it.

2:10
For our first implementation of Merge Sort, we're going to use an array, or

2:15
a Python list.

2:16
While the implementation won't be different conceptually for a linked list,

2:20
we will have to write more code because of list traversal and how nodes are arranged.

2:25
So once we have these concepts squared away, we'll come back to that.

2:29
Let's add a new file here.

2:33
We'll call this merge_sort.py.

2:38
In our file let's create a new function named merge_sort that takes a list.

2:43
And remember when I say list, unless I specify linked list,

2:47
I mean a Python list which is the equivalent of an array.

2:51
So we'll say def merge_sort that takes a list.

2:57
In the Introduction to Algorithms course, we started our study of each algorithm

3:02
by defining the specific steps that comprise the algorithm.

3:05
Let's write that out as a doc string in here,

3:09
the steps of the algorithm so that we can refer to it right in our code.

3:14
This algorithm is going to sort the given list in an ascending order.

3:18
So we'll start by putting that in here as a simple definition.

3:22
Sorts a list in ascending order.

3:27
There are many variations of merge_sort, and

3:30
in the one we're going to implement, we'll create and return a new sorted list.

3:35
Other implementations will sort the list we pass in, and

3:39
this is less typical, in an operation known as sort in place.

3:43
But I think that returning a new list makes it easier to understand the code.

3:48
Now, these choices do have implications though, and

3:50
we'll talk about them as we write this code.

3:53
For our next bit of the doc string, let's write down the output of this algorithm.

3:58
So it returns a new sorted list.

4:02
Merge_sort has three main steps.

4:06
The first is the divide step, where we find the midpoint of the list.

4:10
So I'll say, Divide: Find the midpoint

4:17
of the list and divide into sublists.

4:22
The second step is the Conquer step where we sort the sublists that we created in

4:27
the Divide step.

4:28
So we'll say, recursively sort the sublists created in previous step.

4:36
And finally, the Combine step where we

4:39
merge these recursively sorted sublists back into a single list.

4:44
So merge the sorted sublists created in previous step.

4:53
When we learned about algorithms,

4:55
we learned that a recursive function has a basic pattern.

4:59
First, we start with a base case that includes a stopping condition.

5:04
After that we have some logic that breaks down the problem and

5:07
recursively calls itself.

5:09
Our stopping condition is our end goal, a sorted array.

5:14
Now, to come up with a stopping condition or a base case,

5:17
we need to come up with the simplest condition that satisfies this end result.

5:23
So there are two possible values that fit, a single element list or an empty list.

5:29
Now, in both of these situations, we don't have any work to do.

5:33
If we give the merge_sort function an empty list or

5:36
a list with one element, it's technically already sorted.

5:39
We call this naively sorting.

5:42
So let's add that as our stopping condition.

5:46
We'll say if len(list), if the length of the list,

5:50
is <=1, then we can return the list.

5:53
Okay, so this is a stopping condition.

5:56
And now that we have a stopping condition, we can proceed with the list of steps.

6:02
First, we need to divide the list into sublists.

6:06
To make our functions easier to understand, we're going to put our logic

6:10
in a couple different functions instead of one large one.

6:13
So I'll say, left_half,

6:18
right_half = split(list).

6:23
So here we're calling a split function that splits the list we pass in and

6:28
returns two lists split at the midpoint.

6:31
Because we're returning two lists, we can capture them in two variables.

6:35
Now, you should know that this split function is not something that comes

6:39
built into Python.

6:40
This is a global function that we're about to write.

6:43
Next is the Conquer step where we sort each sublist and

6:48
return a new sorted sublist.

6:50
So we'll say left = merge_sort(left_half),

6:58
And right = merge_sort(right_half).

7:04
This is the recursive portion of our function.

7:07
So here we're calling merge_sort on this divided sublist.

7:11
So we divide the list into two here and then we call merge_sort on it again.

7:15
This further splits that sublist into two.

7:19
In the next passthrough of merge_sort, this is going to be called again and

7:24
again and again, until we reach our stopping condition where we have single

7:29
element lists or empty lists.

7:31
When we've subdivided until we cannot divide anymore,

7:35
then we'll end up with a left and a right half, and we can start merging backwards.

7:41
So let's say, return merge(left, right).

7:46
That brings us to the Combine step.

7:49
Once two sublists are sorted and combined, we can return it.

7:54
Now, obviously none of these functions, merge, merge_sort,

7:57
well merge_ort is written, but merge and split haven't been written.

8:00
So all we're going to do here, if we run it is raise in error.

8:04
So in the next video let's implement the split operation.
You need to sign up for Treehouse in order to download course files.
Sign up