All language subtitles for 6 - Merge Sort English

af Afrikaans
ak Akan
sq Albanian
am Amharic
ar Arabic Download
hy Armenian
az Azerbaijani
eu Basque
be Belarusian
bem Bemba
bn Bengali
bh Bihari
bs Bosnian
br Breton
bg Bulgarian
km Cambodian
ca Catalan
chr Cherokee
ny Chichewa
zh-CN Chinese (Simplified)
zh-TW Chinese (Traditional)
co Corsican
hr Croatian
cs Czech
da Danish
nl Dutch
en English
eo Esperanto
et Estonian
ee Ewe
fo Faroese
tl Filipino
fi Finnish
fr French
fy Frisian
gaa Ga
gl Galician
ka Georgian
de German
el Greek
gn Guarani
gu Gujarati
ht Haitian Creole
ha Hausa
haw Hawaiian
iw Hebrew
hi Hindi
hu Hungarian
is Icelandic
ig Igbo
id Indonesian
ia Interlingua
ga Irish
it Italian
ja Japanese
jw Javanese
kn Kannada
kk Kazakh
rw Kinyarwanda
rn Kirundi
kg Kongo
ko Korean
kri Krio (Sierra Leone)
ku Kurdish
ckb Kurdish (Soranî)
ky Kyrgyz
lo Laothian
la Latin
lv Latvian
ln Lingala
lt Lithuanian
loz Lozi
lg Luganda
ach Luo
mk Macedonian
mg Malagasy
ms Malay
ml Malayalam
mt Maltese
mi Maori
mr Marathi
mfe Mauritian Creole
mo Moldavian
mn Mongolian
sr-ME Montenegrin
ne Nepali
pcm Nigerian Pidgin
nso Northern Sotho
no Norwegian
nn Norwegian (Nynorsk)
oc Occitan
or Oriya
om Oromo
ps Pashto
fa Persian
pl Polish
pt-BR Portuguese (Brazil)
pt-PT Portuguese (Portugal)
pa Punjabi
qu Quechua
ro Romanian
rm Romansh
nyn Runyakitara
ru Russian
gd Scots Gaelic
sr Serbian
sh Serbo-Croatian
st Sesotho
tn Setswana
crs Seychellois Creole
sn Shona
sd Sindhi
si Sinhalese
sk Slovak
sl Slovenian
so Somali
es Spanish
es-419 Spanish (Latin American)
su Sundanese
sw Swahili
sv Swedish
tg Tajik
ta Tamil
tt Tatar
te Telugu
th Thai
ti Tigrinya
to Tonga
lua Tshiluba
tum Tumbuka
tr Turkish
tk Turkmen
tw Twi
ug Uighur
uk Ukrainian
ur Urdu
uz Uzbek
vi Vietnamese
cy Welsh
wo Wolof
xh Xhosa
yi Yiddish
yo Yoruba
zu Zulu
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.