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
Now that we have an implementation of merge sort on two data structures how do they compare? Is one "better"?

0:00
First things first.

0:01
Let's test out our code.

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

0:08
function would actually take up this entire video.

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

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

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

0:23
I'm gonna copy paste this so

0:26
it makes it easier to me to not to have to retype a bunch.

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

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

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

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

0:54
then we'll print this.

0:56
So sorted_linked_list.

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

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

1:08
Hit save and then bring up the console.

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

1:19
We see that linked list we first created.

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

1:27
10 is the tail, 200 is the last one.

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

1:33
It simply adds each one to the head of the list.

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

1:40
And then the sorted_linked_list sorts it out.

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

1:46
Look at that, a sorted linked list.

1:49
Let's visualize this from the top.

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

1:57
44, 15, and 200 as data, respectively.

2:01
Our merge sort function calls split on this list.

2:04
The split function calls size on the list and

2:07
gets back 5 which makes our mid point 2.

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

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

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

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

2:27
1 means we split after node 2.

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

2:33
assign that to right half.

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

2:40
and remove the references between node 2 and node 3.

2:44
So far so good, right?

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

2:50
we have two linked lists.

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

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

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

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

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

3:12
Again, we're back in the merge sort function,

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

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

3:23
we immediately return before we split since we had that stopping condition.

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

3:31
merge sort on the right list as well.

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

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

3:41
we can call merge on them.

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

3:47
attaching a fake head.

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

3:52
Since neither condition is true,

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

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

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

4:06
move the right head pointer forward.

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

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

4:17
On the next iteration,

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

4:23
And we can assign the rest of the left linked list which

4:26
is effectively the single node over to the merge link list.

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

4:36
return the newly merged sorted link list.

4:39
Remember that this point because right head and

4:42
left head pointed to none are wild loop terminated.

4:45
So in this way, we recursively split and

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

4:52
The merge sort algorithm is a powerful sorting algorithm.

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

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

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

5:07
divide and conquer.

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

5:11
There's a teacher at the front of the room and

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

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

5:20
hands it to two students at the front.

5:23
Each of those students split it into two more, and

5:26
handed it to the four students seated behind them.

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

5:33
to compare.

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

5:38
in front of them who repeats the process backwards.

5:41
So ultimately, it's really simple work.

5:43
It's just efficiently delegated.

5:46
Now back to our implementation here.

5:49
Let's talk about run time.

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

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

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

6:01
So in the first implementation of merge sort,

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

6:10
Why?

6:11
The Python list slicing operation, if you remember,

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

6:18
A true implementation of merge_sort runs in quasi linear or

6:22
log linear time that is N times log n.

6:24
So we almost got there but we didn't.

6:28
Now in our implementation of merge_sort on a linked list,

6:31
we introduced the same problem.

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

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

6:43
No big deal.

6:44
Comparing values, also constant time.

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

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

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

7:03
This means that every split operation incurs a big O

7:07
of K cost where K here is the midpoint of the list.

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

7:16
counting up the index until we get to that node.

7:19
Given that overall splits take logarhythmic time, our split function,

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

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

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

7:39
So that one is good.

7:42
That one runs in the expected amount of time.

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

7:48
And that would bring our overall run time, so

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

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

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

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

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

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

8:19
what the run time and space complexities look like, and

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

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

8:30
check out the notes in the teacher's video.

8:32
In the next video, let's wrap this course up.
You need to sign up for Treehouse in order to download course files.
Sign up