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.
[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 up