Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Well done!
You have completed Introduction to Data Structures!
You have completed Introduction to Data Structures!
Preview
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