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.