Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
1
00:00:10,240 --> 00:00:15,820
High in this video we're going to talk about the merge sort algorithm and merge sort is one of the most
2
00:00:15,820 --> 00:00:21,270
popular sorting algorithms that's out there today and there's a number of reasons why.
3
00:00:21,270 --> 00:00:24,820
And there's also some important properties to understand.
4
00:00:24,820 --> 00:00:31,240
One of the biggest reasons why it's so popular is because it's very fast for a sorting algorithm.
5
00:00:31,240 --> 00:00:37,780
If you remember back to insertion sort or this selection sort or any of those that we've discussed in
6
00:00:37,780 --> 00:00:42,250
the past merge or is a order of n log.
7
00:00:42,250 --> 00:00:49,390
And in terms of time complexity which means that it's much faster than some of the other insertion sort
8
00:00:49,510 --> 00:00:57,120
type of algorithms that run at a worst case time complexity at 0 and square.
9
00:00:57,130 --> 00:01:01,000
So that's one thing to remember it's very fast.
10
00:01:01,150 --> 00:01:09,190
And the other thing is it's very easy to understand when we walk through exactly how it works even if
11
00:01:09,190 --> 00:01:15,310
you don't have a strong algorithm or mathematical background I think you'll be able to really capture
12
00:01:15,370 --> 00:01:17,740
exactly how a mergesort works.
13
00:01:17,740 --> 00:01:23,950
So that's something that's very important in my mind when it comes to algorithms because if it's easy
14
00:01:23,950 --> 00:01:30,400
to understand it's going to be a lot easier for you to implement in terms of building the code for it.
15
00:01:30,430 --> 00:01:32,930
The next thing to know is that it's recursive.
16
00:01:32,950 --> 00:01:39,910
So if you've never dealt with recursion or you've never built recursive functions they're actually pretty
17
00:01:39,970 --> 00:01:41,160
similar.
18
00:01:41,200 --> 00:01:43,390
They're pretty easy to understand.
19
00:01:43,510 --> 00:01:52,550
And so I'll draw out exactly how it works so in a program you could do something like call a function
20
00:01:55,510 --> 00:02:04,910
and the function would be something like merge sort.
21
00:02:05,220 --> 00:02:08,910
And then say we're doing Python.
22
00:02:09,060 --> 00:02:11,850
Actually this would say def but you get the point.
23
00:02:11,850 --> 00:02:14,020
There's a function merge sort.
24
00:02:14,160 --> 00:02:22,740
And inside here we're going to be this is where we would call all of the things that we would want that
25
00:02:22,740 --> 00:02:23,750
function to do.
26
00:02:23,790 --> 00:02:28,270
So it could do things like print.
27
00:02:28,410 --> 00:02:36,390
We could add items to an array of different things like that.
28
00:02:36,390 --> 00:02:39,630
We can do if statements all the normal kind of programming things.
29
00:02:39,630 --> 00:02:45,930
The other thing though well what we do with the recursive programs is we actually call
30
00:02:49,230 --> 00:02:54,120
the function itself inside the function.
31
00:02:54,540 --> 00:03:00,120
So we're actually calling merge sort on itself.
32
00:03:00,120 --> 00:03:09,860
And so what that allows us to do is each one of these items will be called again and again and again
33
00:03:09,980 --> 00:03:17,640
when you're calling merge sort because you're calling all of the same properties and methods repeatedly.
34
00:03:17,690 --> 00:03:23,520
And you obviously have to build things in so that the program does have an end at some point.
35
00:03:23,810 --> 00:03:31,760
But what it allows us to do is to break a program down split it apart which addresses number five issue
36
00:03:31,760 --> 00:03:37,820
which we'll talk about in a second and be able to repeat it over and over again as you start to get
37
00:03:37,820 --> 00:03:39,790
into more advanced programming.
38
00:03:40,070 --> 00:03:42,400
Recursion is something that happens a lot.
39
00:03:42,440 --> 00:03:49,850
And being able to understand some of the performance metrics associated with recursive applications
40
00:03:50,210 --> 00:03:52,340
is going to be very important.
41
00:03:52,340 --> 00:03:59,420
The higher you go up in computer science or in mathematics so essentially just understand it it's really
42
00:03:59,420 --> 00:04:06,620
just a program calling itself and will allow you to perform the same task over and over again.
43
00:04:06,630 --> 00:04:14,130
So that's just a very basic idea of what we're cursive functions do.
44
00:04:14,540 --> 00:04:17,840
And they get to me to check marks.
45
00:04:18,020 --> 00:04:21,200
OK so we've gone over the first three and the other thing.
46
00:04:21,200 --> 00:04:22,940
What it is it's a stable sort.
47
00:04:23,150 --> 00:04:28,810
And so what a stable sort is we'll look at just a smaller array right here.
48
00:04:28,820 --> 00:04:39,400
So we'll have three five four three prime and two and just three prime.
49
00:04:39,420 --> 00:04:43,070
So we knew that this is different than the first three.
50
00:04:43,430 --> 00:04:49,120
And so they were to call assort on this in a stable sort.
51
00:04:49,280 --> 00:04:59,480
This would look like this three three primary tube in the front then four and five and that would be
52
00:04:59,480 --> 00:05:01,010
what a stable source looks like.
53
00:05:01,010 --> 00:05:08,570
Which means that this theory is still in front of this theory the same way it is over here.
54
00:05:08,570 --> 00:05:14,780
Now in a unstable sort what you could end up with is something that looks like this
55
00:05:18,540 --> 00:05:29,730
to three prime three four and five sometimes depending on what kind of data you have that doesn't matter.
56
00:05:29,740 --> 00:05:31,060
Other times it can.
57
00:05:31,060 --> 00:05:38,710
So it's very important to know if you're using a stable sort algorithm or if you're using an algorithm
58
00:05:38,830 --> 00:05:43,230
where that means those properties may change.
59
00:05:43,600 --> 00:05:50,020
And so we've got one two three and four and now we're into the last one which is just divide and conquer
60
00:05:50,080 --> 00:05:56,330
and I'm going to go straight into how merge sort works so that we can understand this one.
61
00:05:56,380 --> 00:06:05,130
And so to start off what I'm going to do is just give us a small array of numbers going from 1 to 8.
62
00:06:05,170 --> 00:06:10,450
And so I'm going to go with just three
63
00:06:12,840 --> 00:06:16,090
seven 10
64
00:06:19,420 --> 00:06:22,760
2 3
65
00:06:27,270 --> 00:06:30,550
4 and 1 get almost around the room.
66
00:06:30,720 --> 00:06:38,090
So we have our eight and what divide and conquer does or what merge sort does it uses divide and conquer.
67
00:06:38,250 --> 00:06:42,300
And it literally is as simple as that.
68
00:06:42,300 --> 00:06:49,260
When you abstract it out and this is what it's doing it's going to divide all the elements in the array
69
00:06:49,320 --> 00:06:52,680
and then it's going to perform tasks on them.
70
00:06:52,680 --> 00:06:57,230
So what that would look like is something like this.
71
00:06:57,300 --> 00:07:13,980
Three actually turns almost into its own little mini array then 7 does the same 10 A to our other three
72
00:07:16,290 --> 00:07:24,420
four and one and them so you can see right here we have eight elements and now we're going to start
73
00:07:24,420 --> 00:07:29,900
to do it because they're all spread out now and obviously there would be a process.
74
00:07:29,900 --> 00:07:37,050
And if you're building this with code you would need to create a program that does split amount exactly
75
00:07:37,050 --> 00:07:37,890
like this.
76
00:07:38,010 --> 00:07:46,100
And then what you're going to do is you're going to take and you're going to compare each pair of elements.
77
00:07:46,140 --> 00:07:48,480
So you're going to take each one of these.
78
00:07:48,600 --> 00:07:53,070
And so you'll say is three less than or equal to seven.
79
00:07:53,070 --> 00:07:54,240
It's less than.
80
00:07:54,240 --> 00:08:03,630
So we're going to put this these in their own box and so do 3:7 and then we do the same thing here except
81
00:08:03,630 --> 00:08:06,550
here that actually swap places.
82
00:08:06,600 --> 00:08:15,780
So that's all we're doing is we're comparing each item and then we're putting it in its own broken down
83
00:08:15,780 --> 00:08:19,090
box and then we do the same thing here.
84
00:08:19,710 --> 00:08:28,950
OK now so we've started to put things together and what we'll do now is compare the elements in these
85
00:08:28,950 --> 00:08:32,120
boxes and we'll put it in another one.
86
00:08:32,160 --> 00:08:40,720
So right here we will go and compare three to eight and compare three to 10.
87
00:08:40,920 --> 00:08:44,950
And so we know three is the smaller one out of those.
88
00:08:45,130 --> 00:08:53,740
Then we'd go seven to eight seven to 10 seven the smallest and then eight and then 10.
89
00:08:54,010 --> 00:08:57,660
So that was an easy one because that's already in order.
90
00:08:57,700 --> 00:09:03,030
So we have 3 7 8 and 10 and now we're going to do the same here too.
91
00:09:03,070 --> 00:09:05,230
We're you know it's that it's less than three.
92
00:09:05,260 --> 00:09:07,080
So we look to less than one.
93
00:09:07,090 --> 00:09:08,250
No one's less than that.
94
00:09:08,290 --> 00:09:12,720
So we'd have one is it less than four yes it is.
95
00:09:12,720 --> 00:09:14,220
So we put a 2 there.
96
00:09:14,230 --> 00:09:17,360
Then we look at the three is the three.
97
00:09:17,380 --> 00:09:18,390
Less than four.
98
00:09:18,460 --> 00:09:19,180
Yes it is.
99
00:09:19,180 --> 00:09:22,340
So we put the three there and then have four.
100
00:09:22,360 --> 00:09:31,150
Now if you notice what we've actually done through this process both of these boxes are sorted already.
101
00:09:31,180 --> 00:09:35,680
So we have 3 7 8 and 10 1 2 3 and 4.
102
00:09:36,010 --> 00:09:40,630
And so now all we have to do is do the same thing here.
103
00:09:40,720 --> 00:09:44,500
So we'd say OK is 3 less than 1.
104
00:09:44,500 --> 00:09:45,510
No it's not.
105
00:09:45,520 --> 00:09:54,930
So we know that one's the first element here then is three less than 2 no is 3 less than three.
106
00:09:54,960 --> 00:09:56,440
No it's equal then.
107
00:09:56,440 --> 00:09:59,620
So we're going to put that three there because this is a stable sort.
108
00:10:00,010 --> 00:10:06,690
And then we would go and look at seven and seven would say is seven greater are no less than three.
109
00:10:06,730 --> 00:10:09,730
We'd put that three in seven to four.
110
00:10:09,730 --> 00:10:11,260
Four is.
111
00:10:11,530 --> 00:10:13,120
And then we know that seven is there.
112
00:10:13,150 --> 00:10:20,290
And because there are no more elements in the array we know that the remaining items are the last ones
113
00:10:20,350 --> 00:10:21,440
and there we go.
114
00:10:21,520 --> 00:10:26,390
We have a new array that is fully sorted and we went about it.
115
00:10:26,400 --> 00:10:27,150
Intermediately.
116
00:10:27,190 --> 00:10:35,410
So we went broke it down into each item and then simply sorted those smaller items and start just kept
117
00:10:35,410 --> 00:10:41,670
on putting them together over and over again until we ended up with a completely sorted array.
118
00:10:41,800 --> 00:10:42,460
And that's what.
119
00:10:42,460 --> 00:10:44,440
Divide and conquer is.
120
00:10:44,560 --> 00:10:46,330
And that's exactly how mergesort works.
121
00:10:46,330 --> 00:10:51,950
So please let me know if you have any questions at all about that and I will see you in the next video.
12613
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.