1
00:00:00,650 --> 00:00:05,630
If we go back to the top level, the merge
sort function, what does the runtime
2
00:00:05,630 --> 00:00:08,580
of this function look like, and
what about space complexity?
3
00:00:08,580 --> 00:00:12,070
How does memory usage grow
as the algorithm runs?
4
00:00:12,070 --> 00:00:13,320
To answer those questions,
5
00:00:13,320 --> 00:00:17,380
let's look at the individual steps,
starting with the split function.
6
00:00:17,380 --> 00:00:21,290
In the split function, all we're doing
is finding the midpoint of the list, and
7
00:00:21,290 --> 00:00:23,740
splitting the list at the midpoint.
8
00:00:23,740 --> 00:00:25,940
This seems like a constant time operation.
9
00:00:25,940 --> 00:00:29,210
But remember that the split
function isn't called once.
10
00:00:29,210 --> 00:00:31,940
It's called as many times as we needed to,
11
00:00:31,940 --> 00:00:35,760
to go from the initial list
down to a single element list.
12
00:00:35,760 --> 00:00:38,940
Now, this is a pattern we've
seen a couple of times now, and
13
00:00:38,940 --> 00:00:42,700
we know that overall,
this runs in logarithmic time.
14
00:00:42,700 --> 00:00:44,840
So let's add that as a comment.
15
00:00:44,840 --> 00:00:52,320
So here I'll say,
takes overall O of log n time.
16
00:00:52,320 --> 00:00:55,530
Now there's a caveat here but
we'll come back to that.
17
00:00:55,530 --> 00:00:57,840
So next step is the merge step.
18
00:00:57,840 --> 00:00:59,000
In the merge step,
19
00:00:59,000 --> 00:01:03,200
we've broken the original list
down into single element lists and
20
00:01:03,200 --> 00:01:08,460
now we need to make comparison operations
and merge them back in the reverse order.
21
00:01:08,460 --> 00:01:13,165
For a list of size n, we'll always
need to make an n number of merge
22
00:01:13,165 --> 00:01:17,891
operations to get back from single
element lists to a merge list.
23
00:01:17,891 --> 00:01:23,217
This makes our overall runtime big O
of n times log n because that's an n
24
00:01:23,217 --> 00:01:29,372
number of merge steps multiplied by a log
n number of splits of the original list.
25
00:01:29,372 --> 00:01:33,314
So to our merge step here,
let's add a comment,
26
00:01:33,314 --> 00:01:37,463
we'll say it runs in overall,
whoops there we go.
27
00:01:37,463 --> 00:01:40,311
Runs in overall linear time right?
28
00:01:40,311 --> 00:01:44,182
It takes an n number of steps,
number of merge steps.
29
00:01:44,182 --> 00:01:48,041
But now that we have these two,
so linear here and
30
00:01:48,041 --> 00:01:51,432
logarithmic here we can multiply these and
31
00:01:51,432 --> 00:01:56,140
say that the merge sort function,
the top level function,
32
00:01:56,140 --> 00:02:02,471
we can conclude that the run time of
the overall sorting process is O(n log n).
33
00:02:02,471 --> 00:02:05,540
Now what about the caveat
I mentioned earlier?
34
00:02:05,540 --> 00:02:11,870
So if we go back to our split
function here, right here,
35
00:02:11,870 --> 00:02:16,480
there we go, let's take a look at the way
we're actually splitting the list.
36
00:02:16,480 --> 00:02:20,810
So we're using Python's list
slicing operation here, and
37
00:02:20,810 --> 00:02:23,850
passing in two indexes
where the split occurs.
38
00:02:23,850 --> 00:02:28,847
Now if you go and poke around the Python
documentation, which I've done,
39
00:02:28,847 --> 00:02:33,527
it says that a slicing operation is
not a constant time operation, and
40
00:02:33,527 --> 00:02:38,233
in fact has a run time of O(k),
where k represents the sliced sides.
41
00:02:38,233 --> 00:02:42,133
This means that in reality,
our implementation of split,
42
00:02:42,133 --> 00:02:46,735
this implementation of split,
does not run in logarithmic time, but
43
00:02:46,735 --> 00:02:49,084
(k)(log n) logarithmic time.
44
00:02:49,084 --> 00:02:53,245
Because there's a slice operation for
each split.
45
00:02:53,245 --> 00:02:57,832
This means that our implementation
is much more expensive.
46
00:02:57,832 --> 00:03:02,825
So overall that makes our overall
top level merge_sort function,
47
00:03:02,825 --> 00:03:07,480
not (n log n) (but kn log n),
which is much more expensive.
48
00:03:07,480 --> 00:03:09,672
Now let's get rid of all that.
49
00:03:11,913 --> 00:03:15,790
To fix this we would need to
remove this slicing operation.
50
00:03:15,790 --> 00:03:20,410
Now we can do that by using a technique
we learned in a previous course.
51
00:03:20,410 --> 00:03:24,580
In the introduction to algorithms course
we looked at two versions of binary search
52
00:03:24,580 --> 00:03:28,240
in Python a recursive and
an iterative version.
53
00:03:28,240 --> 00:03:33,187
In the recursive one we use list slicing
with every recursion call, but we achieve
54
00:03:33,187 --> 00:03:37,860
the same end result using an iterative
approach without using list slicing.
55
00:03:37,860 --> 00:03:42,498
Over there we declared two variables
to keep track of the starting, and
56
00:03:42,498 --> 00:03:44,520
ending positions in the list.
57
00:03:44,520 --> 00:03:47,434
We could rewrite merge
sort to do the same, but
58
00:03:47,434 --> 00:03:49,987
I'll leave that as an exercise for you.
59
00:03:49,987 --> 00:03:51,212
If you want some hints, or
60
00:03:51,212 --> 00:03:55,750
if you want any direction I've included a
link in the notes with an implementation.
61
00:03:55,750 --> 00:03:58,190
So that is time complexity.
62
00:03:58,190 --> 00:04:01,123
Now just so we know, before moving on, for
63
00:04:01,123 --> 00:04:05,448
Python here our overall run time
is not what I've listed here.
64
00:04:05,448 --> 00:04:09,938
But this is what the actual runtime of
the merge sort algorithm looks like.
65
00:04:09,938 --> 00:04:12,288
So the merge step runs in linear time.
66
00:04:12,288 --> 00:04:17,081
And the split step takes logarithmic
time for an overall n times log n.
67
00:04:17,081 --> 00:04:19,838
And that is how merge sort actually works.
68
00:04:19,838 --> 00:04:22,300
Okay, so what about space complexity?
69
00:04:22,300 --> 00:04:25,253
The merge sort algorithm
takes linear space.
70
00:04:25,253 --> 00:04:30,278
And this is weird to think about at first,
but as always, a visualization helps.
71
00:04:30,278 --> 00:04:34,132
[SOUND] So if we start at the top
again with our full list and
72
00:04:34,132 --> 00:04:38,478
carry out the split method until
we have single element lists,
73
00:04:38,478 --> 00:04:42,421
each of these new lists take
up a certain amount of space.
74
00:04:42,421 --> 00:04:47,710
So the second level here we have two lists
where each take up an n/2 amount of space.
75
00:04:47,710 --> 00:04:50,920
Now this makes it seem that
the sum of all this space
76
00:04:50,920 --> 00:04:55,210
is the additional space needed for merge
sort, but that's not actually the case.
77
00:04:55,210 --> 00:04:58,230
In reality, there are two
factors that make a difference.
78
00:04:58,230 --> 00:05:03,249
First, not every single one of these
sublists are created simultaneously.
79
00:05:03,249 --> 00:05:07,351
At step two we create
2n by 2 size sublists.
80
00:05:07,351 --> 00:05:13,162
When we move to the next step however,
we don't hold on to the n by 2 sublist and
81
00:05:13,162 --> 00:05:17,143
then create 4n by 4 size sublist for
the next split.
82
00:05:17,143 --> 00:05:21,211
Instead after the 4n by 4
size sublists are created,
83
00:05:21,211 --> 00:05:24,228
the n by 2 ones are deleted from memory.
84
00:05:24,228 --> 00:05:27,250
There's no reason to hold
on to them any longer.
85
00:05:27,250 --> 00:05:32,920
At the second point is that our code
doesn't execute every path simultaneously.
86
00:05:32,920 --> 00:05:34,310
Think of it this way.
87
00:05:34,310 --> 00:05:38,940
When we pass our list to the top
level merge sort function,
88
00:05:38,940 --> 00:05:45,050
our implementation called split which
returns a left half and a right half.
89
00:05:45,050 --> 00:05:50,640
The next line of code then calls
merge sort on the left half again.
90
00:05:50,640 --> 00:05:55,030
This runs the function, the merge
sort function again with a new list.
91
00:05:55,030 --> 00:05:59,790
In that second run of the function split
is called again, we get a second left and
92
00:05:59,790 --> 00:06:00,570
right half, and
93
00:06:00,570 --> 00:06:05,230
then again, like before, we call
merge sort on this left half as well.
94
00:06:05,230 --> 00:06:09,875
What this means is that the code walks
down the left path all the way down
95
00:06:09,875 --> 00:06:15,400
until that initial left half is sorted and
merged back into one array.
96
00:06:15,400 --> 00:06:19,360
Then, it's going to walk all the way down
the right path and sort that until we're
97
00:06:19,360 --> 00:06:24,580
back to that first split
with 2 n/2 sized sublists.
98
00:06:24,580 --> 00:06:28,300
Essentially, we don't run all of
these paths of code at once, so
99
00:06:28,300 --> 00:06:32,480
the algorithm doesn't need
additional space for every sublist.
100
00:06:32,480 --> 00:06:35,820
In fact,
it is the very last step that matters.
101
00:06:35,820 --> 00:06:36,970
In the last step,
102
00:06:36,970 --> 00:06:42,560
the two sublists are merged back into
the new sorted list and returned.
103
00:06:42,560 --> 00:06:48,420
That sorted list has an equal number
of items as the original unsorted list.
104
00:06:48,420 --> 00:06:52,341
And since this is a new list
it means that, at most,
105
00:06:52,341 --> 00:06:57,647
the additional space the algorithm
will require at a given time is n.
106
00:06:57,647 --> 00:07:02,669
Yes, at different points in the algorithm
we require log n amount of space but
107
00:07:02,669 --> 00:07:07,612
log n is smaller than n and so we consider
the space complexity of merge sort to
108
00:07:07,612 --> 00:07:10,646
be linear because that
is the overall factor.
109
00:07:10,646 --> 00:07:12,391
Okay, that was a lot.
110
00:07:12,391 --> 00:07:13,433
So let's stop here.
111
00:07:13,433 --> 00:07:16,534
Don't worry if you've got questions about
merge sort because we're not done yet.
112
00:07:16,534 --> 00:07:21,390
Over the next few videos let's wrap up
this course by implementing merge sort on
113
00:07:21,390 --> 00:07:22,340
a linked list.