**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