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
We've just finished implementing merge sort on a Python list but the beauty of sorting algorithms is in the technique. We aren't restricted to just using a list or an array and in this video we start defining an implementation of merge sort on our custom linked list.
This video doesn't have any notes.
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
Over the last few videos, we implemented
the merge sort algorithm on the array or
0:04
list type in Python.
0:09
Merge sort is probably the most
complicated algorithm we've
0:11
written so far.
0:14
But in doing so, we learned about
an important concept, divide and conquer.
0:15
We also concluded the last
video by figuring
0:19
out the runtime of merge sort
based on our implementation.
0:22
Over the next few videos,
we're going to implement merge sort again,
0:26
this time on the linked list type.
0:30
In doing so,
0:31
we're going to get a chance to see how
the implementation differs based on
0:32
the data structure while still keeping the
fundamentals of the algorithm the same.
0:36
And we'll also see how the runtime may be
affected by the kinds of operations we
0:40
need to implement.
0:45
Let's create a new file that puts our
second implementation of merge sort in.
0:47
So File over here, New File, and
this is going to have a rather long name.
0:51
We'll call this linked_list_merge_sort
with underscores everywhere .py.
0:56
We're going to need the linked list
class that we created earlier, so we'll
1:04
start at the top by importing the linked
list class from the linked_list.py file.
1:09
The way we do that is we'll say
from linked_list import LinkedList.
1:15
Right, so that imports the class.
1:22
Let's test if this works really quick.
1:24
We'll just do something like
l = LinkedList l.add 10 or
1:28
1, doesn't matter, print(l).
1:34
Okay, and if I hit save,
and then down here,
1:38
we'll say python
linked_list_merge_sort.py.
1:42
Okay, it works.
1:47
So this is how we get some of the code,
1:48
how we reuse the code that we've written
in other files into this current file.
1:50
We can get rid of this now.
1:54
Okay, like we did with the first
implementation of merge sort,
1:58
we're going to split the code
up across three functions.
2:01
The main function merge sort,
a split function, and a merge function.
2:05
Now if you were to look up a merge sort
implementation in Python, both for
2:11
a regular list and array, or a linked
list, you would find much more concise
2:15
versions out there, but
they're kinda hard to explain.
2:19
So splitting it up into three will sort
of help it be easier to understand.
2:22
So we'll call this merge_sort
at the top level, and
2:27
this time it's going
to take a linked_list.
2:30
Let's add a docked string
to document the function.
2:34
So we'll say that this function sorts
a linked list in ascending order.
2:37
And like before we'll add
the steps in here, so
2:44
we'll say you first
recursively divide the linked
2:49
list into sublists
containing a single node.
2:54
Then we repeatedly merge these sublists
2:59
to produce sorted sublists
until one remains.
3:05
And then finally, this function
returns a sorted linked list.
3:11
The implementation of this top level
merge function is nearly identical to
3:17
the array or
list version we wrote earlier.
3:22
So first,
we'll provide a stopping condition or two.
3:25
If the size of the list is one, or
3:28
it's an empty list, we'll return
the link list since it's naively sorted.
3:30
So if linked_list.size,
remember that function we wrote,
3:35
equal one, then we'll return linked_list.
3:41
elif linked_list.head Is None,
meaning it's an empty list.
3:46
Then we'll return linked_list as well.
3:53
Okay, next, lets split the linked_list
into a left and right half.
3:56
Conceptually, this is no different but
4:02
in practice we need to
actually traverse the list.
4:05
We'll implement a helper
method to make this easier.
4:08
We will say left_half,
right_half = split(linked_list),
4:11
and once we have two sublists like before,
4:17
we can call merge_sort,
the top level function on each.
4:20
So left = merge_sort(left_half).
4:26
And right = merge_sort on the right_half.
4:33
Finally, we'll merge these two top
level sublists and return it, so
4:39
merge left and right.
4:43
Okay, nothing new here, but in the next
video, let's implement the split logic.
4:45
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