[MUSIC]

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

list type in Python.

Merge sort is probably the most complicated algorithm we've

written so far.

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

We also concluded the last video by figuring

out the runtime of merge sort based on our implementation.

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

this time on the linked list type.

In doing so,

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

the data structure while still keeping the fundamentals of the algorithm the same.

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

need to implement.

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

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

We'll call this linked_list_merge_sort with underscores everywhere .py.

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

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

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

Right, so that imports the class.

Let's test if this works really quick.

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

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

Okay, and if I hit save, and then down here,

we'll say python linked_list_merge_sort.py.

Okay, it works.

So this is how we get some of the code,

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

We can get rid of this now.

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

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

The main function merge sort, a split function, and a merge function.

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

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

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

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

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

this time it's going to take a linked_list.

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

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

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

we'll say you first recursively divide the linked

list into sublists containing a single node.

Then we repeatedly merge these sublists

to produce sorted sublists until one remains.

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

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

the array or list version we wrote earlier.

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

If the size of the list is one, or

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

So if linked_list.size, remember that function we wrote,

equal one, then we'll return linked_list.

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

Then we'll return linked_list as well.

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

Conceptually, this is no different but

in practice we need to actually traverse the list.

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

We will say left_half, right_half = split(linked_list),

and once we have two sublists like before,

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

So left = merge_sort(left_half).

And right = merge_sort on the right_half.

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

merge left and right.

Okay, nothing new here, but in the next video, let's implement the split logic.