1
00:00:00,000 --> 00:00:04,504
In this video, we'll be giving a running
time analysis of the merge sort algorithm.

2
00:00:04,504 --> 00:00:08,788
In particular, we'll be substantiating the
claim that the recursive divide and

3
00:00:08,788 --> 00:00:12,907
conquer merge sort algorithm is better,
has better performance than simpler

4
00:00:12,907 --> 00:00:17,357
sorting algorithms that you might know,
like insertion sort, selection sort, and

5
00:00:17,357 --> 00:00:21,751
bubble sort. So, in particular, the goal
of this lecture will be to mathematically

6
00:00:21,751 --> 00:00:26,090
argue the following claim from an earlier
video, that, in order to sort an

7
00:00:26,090 --> 00:00:30,704
array in numbers, the merge sort algorithm
needs no more than a constant times N log

8
00:00:30,704 --> 00:00:35,416
N operations. That's the maximum number of
lines of executable code that will ever

9
00:00:35,416 --> 00:00:40,901
execute specifically six times n log n
plus six n operations. So, how are we

10
00:00:40,901 --> 00:00:46,134
going to prove this claim? We're going to
use what is called a recursion tree

11
00:00:46,134 --> 00:00:50,574
method. The idea of the recursion tree
method is to write out all of the work

12
00:00:50,574 --> 00:00:54,708
done by the recursive merge sort
algorithm in a tree structure, with the

13
00:00:54,708 --> 00:00:58,899
children of a given node corresponding to the recursive calls made

14
00:00:58,899 --> 00:01:03,146
by that node. The point of this
tree structure is it will facilitate,

15
00:01:03,316 --> 00:01:07,620
interesting way to count up the overall
work done by the algorithm, and will

16
00:01:07,620 --> 00:01:11,867
greatly facilitate, the analysis. So
specifically, what is this tree? So at

17
00:01:11,867 --> 00:01:16,222
level zero, we have a root. And this
corresponds to the outer call of Merge

18
00:01:16,222 --> 00:01:20,546
Sort, okay? So I'm gonna call this level
zero. Now this tree is going to be binary

19
00:01:20,546 --> 00:01:24,443
in recognition of the fact that each
indication of Merge Sort makes two

20
00:01:24,443 --> 00:01:28,767
recursive calls. So the two children
will correspond to the two recursive calls

21
00:01:28,767 --> 00:01:32,718
of Merge Sort. So at the route, we
operate on the entire input array,

22
00:01:32,718 --> 00:01:36,775
so let me draw a big array indicating
that. And at level one, we have one sub

23
00:01:36,775 --> 00:01:41,153
problem for the left half, and another sub
problem for the right half of the input

24
00:01:41,153 --> 00:01:45,166
array. And I'll call these first two
recursive calls, level one. Now of

25
00:01:45,166 --> 00:01:49,901
course each of these two level one
recursive calls will themselves make two

26
00:01:49,901 --> 00:01:54,879
recursive calls. Each operating on then a
quarter of the original input array. So

27
00:01:54,879 --> 00:01:59,713
those are the level two recursive calls,
of which there are four, and this process

28
00:01:59,713 --> 00:02:04,249
will continue until eventually the
recursion bottoms out, in base cases when

29
00:02:04,249 --> 00:02:09,203
they're only an array size zero or one. So
now I have a question for you which I'll,

30
00:02:09,203 --> 00:02:14,098
I'll give you in the form of a quiz which
is, at the bottom of this recursion tree

31
00:02:14,098 --> 00:02:18,694
corresponding to the base cases, what is
the level number at the bottom? So, at

32
00:02:18,694 --> 00:02:24,343
what level do the leaves in this tree
reside? Okay, so hopefully you guess,

33
00:02:24,343 --> 00:02:29,931
correctly guess, that the answer is the
second one, so namely that the number of

34
00:02:29,931 --> 00:02:33,743
levels of the recursion tree is
essentially logarithmic in the size of the

35
00:02:33,743 --> 00:02:37,808
input array. The reason is basically that
the input size is being decreased by a

36
00:02:37,808 --> 00:02:41,620
factor two with each level of the
recursion. If you have an input size of N

37
00:02:41,620 --> 00:02:45,838
at the outer level, then each of the first
set of recursive calls operates on array

38
00:02:45,838 --> 00:02:49,599
of size n over two, at level two,
each array has size n over four, and so on.

39
00:02:49,599 --> 00:02:53,716
Where does the recursion bottom out? Well, down
at the base cases where there's no more

40
00:02:53,716 --> 00:02:57,782
recursion, which is where the input array
has size one or less. So in other words,

41
00:02:57,782 --> 00:03:01,695
the number of levels of recursion is
exactly the number of times you need to

42
00:03:01,695 --> 00:03:06,075
divide N by two, until you get down to a
number that's most one. Recall that's

43
00:03:06,075 --> 00:03:11,042
exactly the definition of a logarithm base
two of n. So since the first level is

44
00:03:11,042 --> 00:03:16,008
level zero and last level is level log
base two of n. The total number of levels

45
00:03:16,008 --> 00:03:20,600
is actually log base two of n plus one.
And when I write down this expression, I'm

46
00:03:20,600 --> 00:03:24,683
here assuming that N is a, is a power of
two. Which is not a big deal. I mean the

47
00:03:24,683 --> 00:03:28,714
analysis is easily extended to the case
where N is not a power of two. And this

48
00:03:28,714 --> 00:03:32,435
way, we don't have to think about
fractions. Log base two of N then is an

49
00:03:32,435 --> 00:03:36,208
integer. Okay so let's return to the
recursion tree. Let me just redraw it

50
00:03:36,208 --> 00:03:42,655
really quick. So again, down here at the
bottom of the tree we have the leaves,

51
00:03:42,655 --> 00:03:47,299
i.e. The base cases where there's no more
recursion. Which when N is the power of

52
00:03:47,299 --> 00:03:52,084
two correspond exactly to single element
arrays. So that's the recursion tree

53
00:03:52,084 --> 00:03:56,024
corresponding to an indication of Merge
Sort. And the motivation for writing

54
00:03:56,024 --> 00:04:00,374
down, for organizing the work performed by
Merge Sort in this way, is it allows us

55
00:04:00,374 --> 00:04:04,314
to count up the work, level by level. And
we'll see that that's a particularly

56
00:04:04,314 --> 00:04:08,613
convenient way to account for all of the
different lines of code that get executed.

57
00:04:08,613 --> 00:04:12,810
Now, to see that in more detail, I need to
ask you to identify a particular pattern.

58
00:04:12,810 --> 00:04:17,505
So, first of all, the first question is,
at a given level, j, of this recursion,

59
00:04:17,505 --> 00:04:22,388
exactly how many distinct sub-problems are
there, as a function of the level j?

60
00:04:22,388 --> 00:04:27,147
That's the first question. The second
question is, for each of those distinct

61
00:04:27,147 --> 00:04:32,155
sub-problems at level j, what is the input
size? So, what is the size of the a-, of

62
00:04:32,155 --> 00:04:36,600
the array, which is passed to a
sub-problem residing at level j of this

63
00:04:36,600 --> 00:04:43,461
recursion tree. So, the correct answer is
the third one. So, first of all, at a

64
00:04:43,461 --> 00:04:48,017
given level, j, there's precisely two to
the j distinct sub-problems. There's one

65
00:04:48,017 --> 00:04:52,457
outermost sub-problem at level zero, it
has two recursive calls, those are the

66
00:04:52,457 --> 00:04:57,359
two, sub-problems at level one, and so on.
In general, since merge short calls itself

67
00:04:57,359 --> 00:05:01,742
twice, the number of sub-problems is
doubling at each level, so that gives us

68
00:05:01,742 --> 00:05:06,143
the expression, two to the j, for the
number of sub-problems at level j. On the

69
00:05:06,143 --> 00:05:10,250
other hand, by a similar argument, the
input size is halving each time. With each

70
00:05:10,250 --> 00:05:14,350
recursive call you pass it half of the
input. That you were given. So at each

71
00:05:14,350 --> 00:05:19,064
level of the recursion tree we're seeing
half of the input size of the previous

72
00:05:19,064 --> 00:05:23,607
level. So after J levels, since we started
with an input size of N, after J levels,

73
00:05:23,607 --> 00:05:28,246
each sub-problem will be operating on an
array of length N over two to the J. Okay,

74
00:05:28,246 --> 00:05:32,725
so now let's put this pattern to use, and
actually count up all of the lines of code

75
00:05:32,725 --> 00:05:36,991
that Merge Sort executes. And as I said
before, the key, the key idea is to count

76
00:05:36,991 --> 00:05:40,990
up the work level by level. Now, to be
clear, when I talk about the amount of

77
00:05:40,990 --> 00:05:45,309
work done at level J, what I'm talking
about is the work done by those 2 to

78
00:05:45,309 --> 00:05:49,521
the J invocations of Merge Sort, not
counting their respective recursive calls.

79
00:05:49,521 --> 00:05:53,840
Not counting work which is gonna get done
in the recursion, lower in the tree. Now,

80
00:05:53,840 --> 00:05:57,733
recall, Merge Sort is a very simple
algorithm. It just has three lines of

81
00:05:57,733 --> 00:06:01,882
code. First there is a recursive call so
we're not counting that, second there is

82
00:06:01,882 --> 00:06:06,184
another recursive call again we're not
counting that a little j and then third we

83
00:06:06,184 --> 00:06:10,434
just invoke the merge subroutine. So really
outside of the recursive calls all that

84
00:06:10,434 --> 00:06:14,684
merge sort does is a single invocation of
merge. Further recall we already have a

85
00:06:14,684 --> 00:06:19,110
good understanding of the number of lines
of code that merge needs. On an input of

86
00:06:19,110 --> 00:06:23,730
size m, it's gonna use, at most, 6m lines
of code. That's an analysis that we did in

87
00:06:23,730 --> 00:06:28,180
the previous video. So, let's fix a level
j. We know how many sub-problems there

88
00:06:28,180 --> 00:06:32,629
are, two to the j. We know the size of
each sub-problem, n over two to the j, and

89
00:06:32,629 --> 00:06:37,307
we know how much work merge needs on such
an input, we just multiply it by six, and

90
00:06:37,307 --> 00:06:41,700
then we just multiply it out, and we get
the amount of work done at a level j.

91
00:06:41,700 --> 00:06:45,550
'Kay? And all of the little adjacent
problems. So here it is in more detail.

92
00:06:45,550 --> 00:06:51,577
Alright. So. We start with just the number
of different sub-problems at level J and

93
00:06:51,577 --> 00:06:56,633
we just notice that, that was at most two
to the J. We also observe that each level

94
00:06:56,633 --> 00:07:01,566
J sub-problem is passed an, an array as
input which has length N over two to the

95
00:07:01,566 --> 00:07:06,260
J. And we know that the merge subroutine,
when given an input, given an array of

96
00:07:06,260 --> 00:07:10,945
size, N over two to the J, will execute
almost six times that many number of lines

97
00:07:10,945 --> 00:07:15,805
of code. So to compute the total amount of
work done at level J, we just multiply the

98
00:07:15,805 --> 00:07:20,375
number of problems times the work done
 sub-problem, per sub problem. And

99
00:07:20,375 --> 00:07:25,061
then something sort of remarkable happens,
where you get this cancellation of the

100
00:07:25,061 --> 00:07:29,513
two, two to the Js. And we get an upper
bound 6N. Which is independent of the

101
00:07:29,513 --> 00:07:34,094
level J. So we do at most six end
operations at the root, we do at most six

102
00:07:34,094 --> 00:07:39,047
end operations at level one, at level two,
and so on, okay? It's independent of the

103
00:07:39,047 --> 00:07:43,195
level. Morally, the reason this is
happening is because of a perfect

104
00:07:43,195 --> 00:07:48,333
equilibrium between two competing forces.
First of all, the number of subproblems is

105
00:07:48,333 --> 00:07:53,058
doubling with each. Level of the recursion
tree but 2ndly the amount of work that we

106
00:07:53,058 --> 00:07:57,699
do per sub-problem is halving with each level
of the recursion tree's, once those two

107
00:07:57,699 --> 00:08:01,758
cancel out. We get an upper bound 6N,
which is independent of the level J. Now,

108
00:08:01,758 --> 00:08:06,174
here's why that's so cool, right? We don't
really care about the amount of work just

109
00:08:06,174 --> 00:08:10,643
at a given level. We care about the amount
of work that Merge Sort does ever, at any

110
00:08:10,643 --> 00:08:14,420
level. But, if we have a bound on the
amount of work at a level which is

111
00:08:14,420 --> 00:08:18,677
independent of the level, then our overall
bound is really easy. What do we do? We

112
00:08:18,677 --> 00:08:22,880
just take the number of levels, and we
know what that is. It's exactly log based

113
00:08:22,880 --> 00:08:27,349
two of N plus one. Remember the levels are
zero through log based two of N inclusive.

114
00:08:27,349 --> 00:08:31,743
And then we have an upper bound 6N for
each of those log n plus one levels. So if

115
00:08:31,743 --> 00:08:36,848
we expand out this quantity, we get
exactly the upper bound that was claimed

116
00:08:36,848 --> 00:08:40,661
earlier namely the number of operations
merge sort executes is at most 6n times

117
00:08:40,661 --> 00:08:47,352
log base 2 of n plus 6n. So that my friends,
is a running time analysis of the merge

118
00:08:47,352 --> 00:08:52,641
sort algorithm. That's why it's running
time is bounded by a constant times N log

119
00:08:52,641 --> 00:08:57,473
N which, especially as N grows large, it
is far superior to the more simple

120
00:08:57,473 --> 00:09:02,385
iterative algorithms like insertion or
selection sort.