Bummer! This is just a preview. You need to be signed in with a Basic account to view the entire video.
Start a free Basic 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.

0:00
[MUSIC]

0:04
Over the last few videos, we implemented the merge sort algorithm on the array or

0:09
list type in Python.

0:11
Merge sort is probably the most complicated algorithm we've

0:14
written so far.

0:15
But in doing so, we learned about an important concept, divide and conquer.

0:19
We also concluded the last video by figuring

0:22
out the runtime of merge sort based on our implementation.

0:26
Over the next few videos, we're going to implement merge sort again,

0:30
this time on the linked list type.

0:31
In doing so,

0:32
we're going to get a chance to see how the implementation differs based on

0:36
the data structure while still keeping the fundamentals of the algorithm the same.

0:40
And we'll also see how the runtime may be affected by the kinds of operations we

0:45
need to implement.

0:47
Let's create a new file that puts our second implementation of merge sort in.

0:51
So File over here, New File, and this is going to have a rather long name.

0:56
We'll call this linked_list_merge_sort with underscores everywhere .py.

1:04
We're going to need the linked list class that we created earlier, so we'll

1:09
start at the top by importing the linked list class from the linked_list.py file.

1:15
The way we do that is we'll say from linked_list import LinkedList.

1:22
Right, so that imports the class.

1:24
Let's test if this works really quick.

1:28
We'll just do something like l = LinkedList l.add 10 or

1:34
1, doesn't matter, print(l).

1:38
Okay, and if I hit save, and then down here,

1:42
we'll say python linked_list_merge_sort.py.

1:47
Okay, it works.

1:48
So this is how we get some of the code,

1:50
how we reuse the code that we've written in other files into this current file.

1:54
We can get rid of this now.

1:58
Okay, like we did with the first implementation of merge sort,

2:01
we're going to split the code up across three functions.

2:05
The main function merge sort, a split function, and a merge function.

2:11
Now if you were to look up a merge sort implementation in Python, both for

2:15
a regular list and array, or a linked list, you would find much more concise

2:19
versions out there, but they're kinda hard to explain.

2:22
So splitting it up into three will sort of help it be easier to understand.

2:27
So we'll call this merge_sort at the top level, and

2:30
this time it's going to take a linked_list.

2:34
Let's add a docked string to document the function.

2:37
So we'll say that this function sorts a linked list in ascending order.

2:44
And like before we'll add the steps in here, so

2:49
we'll say you first recursively divide the linked

2:54
list into sublists containing a single node.

2:59
Then we repeatedly merge these sublists

3:05
to produce sorted sublists until one remains.

3:11
And then finally, this function returns a sorted linked list.

3:17
The implementation of this top level merge function is nearly identical to

3:22
the array or list version we wrote earlier.

3:25
So first, we'll provide a stopping condition or two.

3:28
If the size of the list is one, or

3:30
it's an empty list, we'll return the link list since it's naively sorted.

3:35
So if linked_list.size, remember that function we wrote,

3:41
equal one, then we'll return linked_list.

3:46
elif linked_list.head Is None, meaning it's an empty list.

3:53
Then we'll return linked_list as well.

3:56
Okay, next, lets split the linked_list into a left and right half.

4:02
Conceptually, this is no different but

4:05
in practice we need to actually traverse the list.

4:08
We'll implement a helper method to make this easier.

4:11
We will say left_half, right_half = split(linked_list),

4:17
and once we have two sublists like before,

4:20
we can call merge_sort, the top level function on each.

4:26
So left = merge_sort(left_half).

4:33
And right = merge_sort on the right_half.

4:39
Finally, we'll merge these two top level sublists and return it, so

4:43
merge left and right.

4:45
Okay, nothing new here, but in the next video, let's implement the split logic.
You need to sign up for Treehouse in order to download course files.
Sign up