Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Preview
Start a free Courses trial
to watch this video
Before we implement merge sort in code lets understand how it works conceptually.
Resources
Related Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign upRelated Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign up
[MUSIC]
0:00
Now that we've seen two different data
structures, let's circle back and
0:04
apply what we know about
algorithms to these new concepts.
0:08
One of the first algorithms you
learned about was binary search.
0:11
And we learned that with binary
search there was one pre-condition.
0:14
The data collection needs to be sorted.
0:18
Over the next few videos let's
implement the merge sort algorithm,
0:20
which is one of many sorting algorithms
on both arrays or Python lists and
0:23
the singly linked list we just created.
0:28
This way we can learn a new sorting
algorithm that has real world use cases
0:30
and see how a single algorithm can be
implemented on different data structures.
0:35
Before we get into code, let's take a look
at how merge sort works conceptually,
0:40
and we'll use an array
to work through this.
0:45
We start with an unsorted
array of integers, and
0:48
our goal is to end up with an array
sorted in ascending order.
0:51
Merge Sort works like binary sort
by splitting up the problem into
0:55
sub-problems, but
it takes the process one step further.
0:59
On the first pass, we're going to split
the array into two smaller arrays.
1:03
Now in binary search,
one of these subarrays would be discarded.
1:07
But that's not what happens here.
1:11
On the second pass, we're going to split
each of those subarrays into further,
1:12
smaller, evenly sized arrays.
1:17
And we're going to keep doing this until
we're down to single element arrays.
1:19
After that,
the Merge Sort algorithm works backwards,
1:23
repeatedly merging the single element
arrays, and sorting them at the same time.
1:27
Since we start at the bottom,
by merging two single element arrays,
1:32
we only need to make a single comparison
to sort the resulting merged array.
1:37
By starting with smaller arrays that
are sorted as they grow, Merge Sort has
1:42
to execute fewer sort operations than
if it sorted the entire array at once.
1:47
Solving a problem like this by recursively
breaking down the problem into
1:52
subparts until it is easily solved is an
algorithmic strategy known as divide and
1:56
conquer.
2:01
But instead of talking about all of this
in the abstract, let's dive into the code.
2:02
This way, we can analyze the run
time as we implement it.
2:06
For our first implementation of Merge
Sort, we're going to use an array, or
2:10
a Python list.
2:15
While the implementation won't be
different conceptually for a linked list,
2:16
we will have to write more code because of
list traversal and how nodes are arranged.
2:20
So once we have these concepts
squared away, we'll come back to that.
2:25
Let's add a new file here.
2:29
We'll call this merge_sort.py.
2:33
In our file let's create a new function
named merge_sort that takes a list.
2:38
And remember when I say list,
unless I specify linked list,
2:43
I mean a Python list which is
the equivalent of an array.
2:47
So we'll say def merge_sort
that takes a list.
2:51
In the Introduction to Algorithms course,
we started our study of each algorithm
2:57
by defining the specific steps
that comprise the algorithm.
3:02
Let's write that out as
a doc string in here,
3:05
the steps of the algorithm so
that we can refer to it right in our code.
3:09
This algorithm is going to sort
the given list in an ascending order.
3:14
So we'll start by putting that
in here as a simple definition.
3:18
Sorts a list in ascending order.
3:22
There are many variations of merge_sort,
and
3:27
in the one we're going to implement,
we'll create and return a new sorted list.
3:30
Other implementations will
sort the list we pass in, and
3:35
this is less typical,
in an operation known as sort in place.
3:39
But I think that returning a new list
makes it easier to understand the code.
3:43
Now, these choices do have
implications though, and
3:48
we'll talk about them
as we write this code.
3:50
For our next bit of the doc string, let's
write down the output of this algorithm.
3:53
So it returns a new sorted list.
3:58
Merge_sort has three main steps.
4:02
The first is the divide step,
where we find the midpoint of the list.
4:06
So I'll say, Divide: Find the midpoint
4:10
of the list and divide into sublists.
4:17
The second step is the Conquer step where
we sort the sublists that we created in
4:22
the Divide step.
4:27
So we'll say, recursively sort
the sublists created in previous step.
4:28
And finally, the Combine step where we
4:36
merge these recursively sorted
sublists back into a single list.
4:39
So merge the sorted sublists
created in previous step.
4:44
When we learned about algorithms,
4:53
we learned that a recursive
function has a basic pattern.
4:55
First, we start with a base case
that includes a stopping condition.
4:59
After that we have some logic
that breaks down the problem and
5:04
recursively calls itself.
5:07
Our stopping condition is our end goal,
a sorted array.
5:09
Now, to come up with a stopping
condition or a base case,
5:14
we need to come up with the simplest
condition that satisfies this end result.
5:17
So there are two possible values that fit,
a single element list or an empty list.
5:23
Now, in both of these situations,
we don't have any work to do.
5:29
If we give the merge_sort
function an empty list or
5:33
a list with one element,
it's technically already sorted.
5:36
We call this naively sorting.
5:39
So let's add that as
our stopping condition.
5:42
We'll say if len(list),
if the length of the list,
5:46
is <=1, then we can return the list.
5:50
Okay, so this is a stopping condition.
5:53
And now that we have a stopping condition,
we can proceed with the list of steps.
5:56
First, we need to divide
the list into sublists.
6:02
To make our functions easier to
understand, we're going to put our logic
6:06
in a couple different functions
instead of one large one.
6:10
So I'll say, left_half,
6:13
right_half = split(list).
6:18
So here we're calling a split function
that splits the list we pass in and
6:23
returns two lists split at the midpoint.
6:28
Because we're returning two lists,
we can capture them in two variables.
6:31
Now, you should know that this split
function is not something that comes
6:35
built into Python.
6:39
This is a global function
that we're about to write.
6:40
Next is the Conquer step where
we sort each sublist and
6:43
return a new sorted sublist.
6:48
So we'll say left = merge_sort(left_half),
6:50
And right = merge_sort(right_half).
6:58
This is the recursive
portion of our function.
7:04
So here we're calling merge_sort
on this divided sublist.
7:07
So we divide the list into two here and
then we call merge_sort on it again.
7:11
This further splits that sublist into two.
7:15
In the next passthrough of merge_sort,
this is going to be called again and
7:19
again and again, until we reach our
stopping condition where we have single
7:24
element lists or empty lists.
7:29
When we've subdivided until
we cannot divide anymore,
7:31
then we'll end up with a left and a right
half, and we can start merging backwards.
7:35
So let's say, return merge(left, right).
7:41
That brings us to the Combine step.
7:46
Once two sublists are sorted and
combined, we can return it.
7:49
Now, obviously none of these functions,
merge, merge_sort,
7:54
well merge_ort is written, but
merge and split haven't been written.
7:57
So all we're going to do here,
if we run it is raise in error.
8:00
So in the next video let's
implement the split operation.
8:04
You need to sign up for Treehouse in order to download course files.
Sign upYou need to sign up for Treehouse in order to set up Workspace
Sign up