First things first.

Let's test out our code.

Now we'll keep it simple because writing a robust verified

function would actually take up this entire video.

Instead, I'll leave that to you to try as homework.

At the very end let's create a new linked list.

Let's add a few nodes to this so l_add.

I'm gonna copy paste this so

it makes it easier to me to not to have to retype a bunch.

So I'll add 10, and then say 2, 44, 15, and something like 200.

Then we'll go ahead and print l so that we can inspect this list.

Next let's declare a variable here so we'll call this sorted_linked_list.

And to this we're going to assign the result of calling merge sort on l and

then we'll print this.

So sorted_linked_list.

Since we've taken care of all the logic, we know that this gets added in as nodes.

And then, let's see what this looks like.

Hit save and then bring up the console.

We're going to type up python linked_list_merge_sort.py and then enter.

We see that linked list we first created.

Remember that what we add first, that eventually becomes the tail.

10 is the tail, 200 is the last one.

So 200 is the head because I'm calling add.

It simply adds each one to the head of the list.

So here we have 10, 2, 44, 15, and 200 in the order we added.

And then the sorted_linked_list sorts it out.

So it's 2, 10, 15, 44, and 200.

Look at that, a sorted linked list.

Let's visualize this from the top.

We have a linked list containing 5 nodes, with integers 10, 2,

44, 15, and 200 as data, respectively.

Our merge sort function calls split on this list.

The split function calls size on the list and

gets back 5 which makes our mid point 2.

Using this midpoint, we can split the list using the node at index method.

Remember that when doing this, we deduct one from the value of mid.

So we're going to split here using an index value of 1.

Effectively this is the same, since we're starting with an index value of 0,

1 means we split after node 2.

We assign the entire list to left half, then create a new list and

assign that to right half.

We can assign node 3 at index value 2 as the head of the right list,

and remove the references between node 2 and node 3.

So far so good, right?

Now we're back in the merge_sort function after having called split, and

we have two linked lists.

Let's focus on just the left half, because if you go back and

and look at our code, we're going to call merge_sort on the left linked list again.

This means the next thing we'll do is run through that split process.

Since this is a linked list containing two nodes, this means that split

is going to return a new left and right list, each with one node.

Again, we're back in the merge sort function,

which means that we call merge sort on this left list again.

Since this is a single node link list, on calling merged sort on it,

we immediately return before we split since we had that stopping condition.

So we go to the next line of code which is calling

merge sort on the right list as well.

But again, we'll get back immediately because we hit that stopping condition.

Now that we have a left and right that we get back from calling merge sort,

we can call merge on them.

Inside the merge function, we start by creating a new linked list and

attaching a fake head.

Then we evaluate whether the left or the right head is none.

Since neither condition is true,

we go to the final step where we evaluate the data in each node.

In this case, the data in the right node is less than the left node.

So we assign the right node as the next node in the merge link list and

move the right head pointer forward.

In the merge link list, we move our current pointer forward

to this new node we've added and that completes one iteration of the loop.

On the next iteration,

right head now points to none since that was a single node list.

And we can assign the rest of the left linked list which

is effectively the single node over to the merge link list.

Here we discard the fake head, move the next node up to be the correct head and

return the newly merged sorted link list.

Remember that this point because right head and

left head pointed to none are wild loop terminated.

So in this way, we recursively split and

repeatedly merge sublists until we're back with one sorted linked list.

The merge sort algorithm is a powerful sorting algorithm.

But ultimately, it doesn't really do anything complicated.

It just breaks the problem down until it's really simple to solve.

Remember the technique here which we've talked about before is called

divide and conquer.

So I like to think of merge sort in this way.

There's a teacher at the front of the room and

she has a bunch of books that she needs to sort into alphabetical order.

Instead of doing all the work herself, she splits that pile into two and

hands it to two students at the front.

Each of those students split it into two more, and

handed it to the four students seated behind them.

As each student does this eventually a bunch of single students has two books

to compare.

And they can sort it very easily and hand it back to the student who gave it to them

in front of them who repeats the process backwards.

So ultimately, it's really simple work.

It's just efficiently delegated.

Now back to our implementation here.

Let's talk about run time.

So far other than the node swapping we had to do,

it seems like most of our implementation is the same right?

In fact it is, including the problems that we run into in the list version as well.

So in the first implementation of merge sort,

we thought we had an algorithm that ran in big O of N login, but turns out we didn't.

Why?

The Python list slicing operation, if you remember,

actually takes up some amount of time amounting to big O of K.

A true implementation of merge_sort runs in quasi linear or

log linear time that is N times log n.

So we almost got there but we didn't.

Now in our implementation of merge_sort on a linked list,

we introduced the same problem.

So if we go back up to the split function, this is where it happens.

Now, swapping node references, that's a constant time operation.

No big deal.

Comparing values, also constant time.

The bottleneck here, like list slicing, is in splitting a link list at the mid point.

If we go back to our implementation, you can see here that we use the noted

index method which finds the node we want by traversing the list.

This means that every split operation incurs a big O

of K cost where K here is the mid-point of the list.

Effectively N by 2 because we have to walk down the list,

counting up the index until we get to that node.

Given that overall splits take logarhythmic time, our split function,

just like the one we wrote earlier, incurs a cost of big O of k log n.

So here we'll say Take Takes O(k log n).

Now the merge function, also like the one we wrote earlier, takes linear time.

So that one is good.

That one runs in the expected amount of time.

So here, we'll say it runs in linear time.

And that would bring our overall run time, so

up at the merge_sort function We can say this runs in O(kn log n).

It's okay though, this is a good start.

And one day when we talk about constant factors and look at ways

we can reduce the cost of these operations using different strategies,

we can come back and reevaluate our code to improve our implementation.

For now, as long as you understand how merge sort works conceptually,

what the run time and space complexities look like, and

where the bottle necks are in your code, that's plenty of stuff.

If you're interested in learning more about how we would solve this problem,

check out the notes in the teacher's video.

In the next video, let's wrap this course up.