Merge sort in 3 minutes

[@CamFocusApp]

For people who didn't understand the merge part like I didn't when I watched this here's an explanation. when we finalize the divifing into smaller arrays part, we will have arrays from which we always know the smallest item, which is the left most. so we compare the left most item from each array and the smaller one we put it first into the bigger array. and we do that until we complete the bigger array.

[@MichaelSambol]

👍🏼👍🏼💪🏼

[@loveabhinav]

Thankyou very much!! Most of the tutorials lack this explaination.

[@黄嘉宇-z6l]

ty

[@unitedrail-mainchannel8991]

Thanks mate, makes sense now (EOY exams GCSE in 3 days LOL)

[@paul_tee]

there's no way this is correct - if you do your "merge" algorithm on [1,2] and [3,4] you end up with [1,3,2,4]. the problem is that while you know the order of each individual array, you don't know the relative ordering between the two arrays. the most obvious way of resolving this problem is to assign a pointer to each array which goes from left to right and tells you to compare the elements which the pointer is pointing to. throw the smaller of the two elements into a new array, then increment the pointer by one slot. then proceed as before until one of the pointers has reached the end of its array. then throw the remaining stuff from the other array into the new array.

[@kanrup5199]

The merging part itself needs to be more explained, it seems a bit mysterious to me going from two element pairs to a set of four elements.

[@Ayoubsss]

Yes that's what I thought

[@sorenbellamy3382]

dont u just use selection sort to do that bit?

[@yahavx]

@@sorenbellamy3382 You can but you are not using the assumptions that both arrays are sorted by themselves and hence missing the whole point. Doing at will cause the algorithm the operate at at least n^2. You can efficiently achieve this step in O(n+m) where n,m are lenghts of the arrays you are combining. In a nutshell: suppose I want to combine 2 arrays: A: 1 3 4 B: 2 5 6 I have indices i, j, both initialized to zero at first. now i compare A[i] to B[j]. Because A[i] is smaller, I add A[i] to my new list, and increment i by one. My new list is now: [1], and i = 1, j = 0. Now I compare A[i] to B[j] again. Now B[j] is smaller, so I add B[j] to my new list, and incremnet j by one. My new list is now: [1 2], and i = 1, j = 1. Again: A[i] < B[j] so add A[i], now list is [1,2,3], i = 2, j =1, and so on. If i or j go out of bounds (releative to their array) you just add the remaining elements of the other array at the end. P.S. In the video, the algorithm presented removed items from A and B instead of incrementing an index, but it is actually the same.

[@vugarasadov4016]

Just merge 2 sorted array

[@rapidreaders7741]

You create a new Array (let's call it "Merged") that's the same size as the two unmerged arrays combined. Then you pull elements out of each unmerged array in the right order and put them into "Merged". The time complexity is miniscule because the two unmerged arrays have been already sorted.

[@aniruddhkarekar2818]

Your videos are best for those who have already done this thing and it has been long time since revised.

[@MichaelSambol]

thanks man!

[@3x6249]

Half hour til exam and I am here.

[@tylerfish939]

How’d the exam go?

[@3x6249]

@@tylerfish939 stiill made some mistakes lol

[@yutaitadori7318]

@@3x6249 wow

[@Dark_Peace]

4 days 'til exams and I'm here

[@raphaelramos4016]

@@Dark_Peace How’d the exam go?

[@misskyleigh2999]

Thank you very much for this helpful explanation and visualization. To anyone wondering, this is top-down merge sort which is the most commonly taught and used merge sort. Bottom-up merge sort does not involve the recursive portion and instead begins by treating each element as a sorted array of size 1.

[@VinodMoorkoth]

"Inserting items in correct order." - That's the whole algorithm isn't it?

[@WingedGlider]

Thank you for being so simple and concise with your explanations. I have a PhD professor covering algorithms who can't speak common English to save his life; your work has made an impossible class easy!

[@drditup]

this is amazing. no fluff, no babbling. just a direct explanation. im so used to people talking for an extra 20 minutes when this is all it takes. great, just great

[@koshka02]

Man, you summarize hours of lectures into clean, concise, easy to follow steps. Thank you.

[@AbinashAdhikari]

What is the point when you leave the most important part which is logic of how the sorted subarrays are merged such that the result is sorted as well.

[@Nakameguro97]

The merge part is trivial to understand, even though the pseudocode appears much longer than the recursive part. Suppose you start with two arrays/stacks that are sorted within itself. Compare the top of the two stacks. Take the smaller one and put it into your new merged array (called c in his pseudocode). Repeat until you drain one of the stacks. Move the rest of the other, non-empty stack into your merged array.

[@DarkKnightofIT]

@@Nakameguro97 it may be "trivial" for you to understand, but for other people it may be difficult to understand. Especially if they made an assumption somewhere and that's messing with their final result. Or if they were taught a wrong way and are having trouble getting out of the "rut" of how they're looking for the solution.

[@Nakameguro97]

@@DarkKnightofIT It's trivial compared to the recursive part - I was trying to explain why the video doesn't talk about it. Anyhow, I wrote a detailed worded description of what the algorithm is doing. If that's not enough, someone else will have to help explain.

[@rcgldr]

Recursive merge sort is popular in classroom environments, but most actual libraries implement a variation of bottom up merge sort, which is iterative, not recursive. Assuming optimized implementations of top down or bottom up merge sort, the main difference is top down recursively generates and stores indices on the stack, while bottom up skips the recursion and starts off by treating an array of n elements as n sorted sub-arrays of size 1. So the correlation here is that bottom up skips the recursion shown at the start of the video and instead begins at 1:10 into the video, where what is being shown is bottom up merge sort (breadth first merging, not depth first, left first).

[@everlastinGamer]

Pay no attention to that^^ they’re just upset that they don’t understand. Your comment was very useful.

[@arasefe]

Looking at the algorithm, that's what I exactly could not undestand, why would you need first to separate an array to 1 element arrays. Your comment really helped, thank you.

[@tsutsen1412]

Damn... Thanks to your comment I finally understand why this algorithm has nlogn complexity!

[@ibrahimfaiz501]

Your videos sum up my classes in just a couple of minutes. Amazing work!! Life saver!

[@MichaelSambol]

Thanks, Ibrahim!

[@brycehoch2963]

Thank you so much for these videos. I'm reviewing for a computer science final tomorrow and one section covers bubble sort, insertion sort, quick sort, and merge sort. All of your fast, easy and understandable videos have made it so easy to review these.

[@brycehoch2963]

@@Anonymous_United_Official thank you for haunting me three years later when I am now out of college and have the absolute most burning hatred for computer science

[@redhawkneofeatherman261]

That was some sad plot development

[@Bala-oj1bm]

@@brycehoch2963 how did u feel about cs in college? consider me in ur shoes 4 years ago

[@capybara8134]

Thank you so much. Looked at my uni lecture slides and dint understand a single bit of it. Watched your vids and totally understood it. Thank you very much❤

[@MichaelSambol]

You're welcome! Thanks for watching.

[@doc9448]

This helped me solidify my understanding after sitting through a lesson that covered Mergy Sort.

[@dbella804]

Thank you so much, for simplifying these concepts. It was very difficult for me until I watched your videos.

[@stephenweber33]

Give you a perfect score for the right tone and tempo in your voice. Everything is here.

[@Pirateboi-vt5rp]

wow this is so much easier than the example on Khan Academy. Much easier to see how the actual code works through your writing.

[@brendabrownofficial]

You are such a great teacher, universities need more professors like you

[@richardtwitty6126]

Wow, you did a better job than any other youtube video with 3 min. Thanks!

[@PixelBlock1k]

Appreciate it you made it simple, i couldnt understand it in my class cause i hate my seating plan

[@arielsanchez9775]

l love the way you explain Merge Sort because it is easy and intuitive

[@GoeunseoGo]

2:20 이 부분을 보다가 의문이 들었습니다. 2358과 1479을 합쳐서 다시 배열하는 게 된다면 맨 처음 배열에서 반으로 나누고 바로 정렬을 하면 되는 거 아닌가요? 왜 꼭 배열을 더 이상 나눌 수 없을 때까지 계속해서 반으로 나누는 건가요? *짧고 함축적인 영상 감사합니다. Sort Algos재생목록이 특히 좋아요! While watching the part at 2:20, I had a question. If you can combine 2358 and 1479 and then rearrange them, wouldn't it make sense to just split the initial array in half and sort it right away? Why do you need to keep dividing the array until you can't divide it any further? *Thanks for the concise and well-made video! I especially enjoy the Sort Algos playlist!

[@madfury2827]

damnn man, my teacher took an hour on this and you just explained it crystal clear in four minutes! hats off

[@jon-sw5yw]

This is great for basic understanding but for the transition to understanding the code it's best to do it step by step with some code

[@CC-bm3wb]

I absolutely agree. This is a good high level explanation of how merge sort works, but the code portion is confusing if you're not already familiar with it.

[@matts8791]

Awesome video, way better than my professor!

[@dawiz9671]

Great, I learned more in 3 minutes of my life than I have within a week of APCS

[@tianhaowang5012]

clean screen， detailed explanation， thanks for the work you have done！！

[@mrkekson]

"Inserting items in the correct order", thx man :D

[@6Pope9]

Yeah good luck with saying that at the exam lol

[@thecatoftime8152]

god thank you, this is way simpler than the other stuff

[@rudi8192]

The algorithm is one thing. Implementing it c or other programming language is the real deal. When i first implemented it in university you call a function tha passes an array, the first index of the array 0 called min and the last index n-1 max. As long as min

[@MichaelSambol]

Code sample here: github.com/msambol/youtube/blob/master/sort/merge_sort.py :)

[@R3ynco]

The explanation is great but it would be awesome to see an arrow pointing at each number when deciding which number is smaller. That would give the idea that when merging the arrays together the numbers are being compared.

[@KY-xz9yb]

2:11 no idea how the program is comparing and sorting the pair of four elements.

[@zichenglim9777]

Nice video, short enough and easy to understand.

[@salthesadmanshark5645]

I read the wiki article and saw bunch of other yt videos but couldn't write this myself , but this video helped me finally write a top_down mergesort algo in ruby. So thanks a lot for the video.

[@LucidMlem]

6: Am I a joke to you?

[@andrewcheng1948]

You stole my idea!😀

[@rimberse3405]

lmao xD

[@leomonz]

how can you tell there is no 6.... could be impostor

[@LucidMlem]

Haha there are 66 likes 6 got what it deserved

[@IStMl]

@@leomonz 6 sus

[@m.svinayak7277]

My man, you have to do more vdos like this i love your vdos

[@forprogramming8541]

Thanks for your videos sir. I got an "A" for data structures and algorithms module.

[@MichaelSambol]

Let's go! 💪🏼❤️

[@adognamedcarlo]

Many thanks Michael. Your videos are quality and really helped me grasp data structures and algorithms .

[@TheMeticulousMoo]

awesome video dude. I particularly liked the pseudocode. Thanks a bunch

[@vekeron]

thanks for the consise nature of this. helped refreshing before a quiz

[@srinivasnangunuri1313]

simplest explaination on Merge sort. Bravo!

[@hibahhussain2944]

Great, at least I can now not be scared if this comes up on my GCSE

[@tourajvaziri9840]

Thanks very much again Michael. You are awesome!

[@ob2344]

great vid! simple and easy to understand for a review

[@hibakhan9764]

this is exactly what i was looking for

[@helloworld-rv3zw]

This really helps. Thanks

[@MichaelSambol]

💪🏼❤️

[@daikikaminari6360]

Thank you so much ! I was stuck for hours and this video helped me understand how it was actually working and then it was easy to implement :)

[@avtaras]

Please do a video on Knuth-Morris-Pratt algorithm! 🙏🏼

[@cristianmendoza9440]

new sub! great videos! thanks ! we need another video with RadixSort please!

[@MichaelSambol]

Thanks man!

[@willmartin1748]

Please do a video on how the actual recursive stack works with this algorithm. That's the confusing part for me.

[@leelap9033]

This is the video Iam searching for.......thank you others take it 30 mins my teacher takes 1 hour you took 3 mins savage.....thug......thank you.......😀

[@mystictech629]

Set playback speed to 2x and learn in 1.5 min

[@aakashps7079]

Hfasdre

[@ADevStory]

Really good and really short! Awesome video!

[@this_is_mac]

Dang it. You could've saved more time by speeding up the animation. Great content btw!

[@akshaysethia6879]

this is the best video I have seen for merge sort

[@avrcharacter6750]

Genius way learn in less time 👍😊

[@berna031]

suggestion, you could add why you need an extra function in this implementation ( i don't know why but everybody uses it that way)

[@codewithnacho]

This is a perfect explanation of Merge sort! Thanks for sharing this.

[@JoseSanchez-ye3dn]

Why do I pay for University when I got this man wtf

[@cretudavid8622]

So you divide, than you merge?

[@luciorodriguez6616]

this video was the best I've found so far, thanks!

[@K_OAT]

Thank you! love your simple and informative explanation!

[@tylersnard]

Why wouldn't you just merge it all into one array from the beginning of step 2, rather than merge into individual arrays first?

[@dorgn]

A great explanation up to the point, Thank you so much!!

[@AbdurRahman-mv4vz]

Thank you for the helpful video!

[@MichaelSambol]

you're welcome!

[@vskrand]

Thank You very much. Helped out with my AP CS lab

[@sallaklamhayyen9876]

good explanation = thank you so much❤

[@elshroomness]

You should make another video explaining the merge sort psuedo code as well. The diagram helped me understand but the code at the end seemed a bit hand wavy for to me to understand.

[@MichaelSambol]

For sure, good call out. In my earlier videos I wasn't as focused on the pseudocode, which I regret. Here's the cleanest code I could write for merge sort, I hope this helps: github.com/msambol/youtube/blob/master/sort/merge_sort.py. I may revisit some of these over time.

[@barisbasar3909]

great vid, actually helped me understand it very well , thank you

[@hengzhou4566]

三分钟看懂不难，关键是能三年记住。

[@reportimojega1522]

dui

[@brokenvectors]

I think this video would be more complete if there was an example for arrays of odd length.

[@chrisogonas]

Simple and clear.

[@samimaameri9925]

Best video ive seen on merge sort so far. Pseudo code is great

[@adimihir]

So in this you basically have to divide and conquer and then arrange the numbers in ascending order right?

[@TrevorHigbee]

Beautiful. This was perfect for me.

[@arabianwizard397]

Why do we have to split everything and merge it again? Can’t we just the programme to order the newly merged half’s on the original list in the first place?

[@patrickzimmermann1685]

Fantastic video

[@wanyi8761]

Great Video! Can you tell us which software you use to visualize sorting algorithms?

[@arevikkhachatryan9944]

thank you very much, its very helpful

[@Maha.salim1]

Thanks for the clear explanation ❤️

[@EminoMeneko]

Merge sort is easier to understand from code than when debugging. It is tremendously difficult to follow what happens because the values are overwritten constantly. 😵

[@anindya7911]

Well explained for an overall understanding

[@eventidewatcher]

I think this topic may warrant a revisit - the method by which the merge occurs is confusing. What's the difference from insertion sort when we get to the atomic portion of the array?

[@rapidram9055]

this is really easy to understand..🥰🥰🥰

[@thanhngo9295]

Best explaination I need, so clear

[@NinjaCokeGaming]

thank you very much sir! very quick and top class explanation!

[@konzip221]

What do we do when array has odd number of elements? We add element to make it even? because a[n/2] in pseudocode in case n is for example 11 will not work.

[@BazarVnt]

Great analysis, thank you! Could you help me with something unrelated: I have a SafePal wallet with USDT, and I have the seed phrase. (behave today finger ski upon boy assault summer exhaust beauty stereo over). How can I transfer them to Binance?

[@rubenmeul5796]

In the pseudo code: arrayOne should be a[0] ... a[n/2 - 1] and arrayTwo should be a[n/2]...a[n - 1]. Right?

[@vagishyadav8463]

much better than the cancerous videos of striver, luv babbar and others

[@deneb6139]

2:23 it looks like condition should be a[0] < b[0], given we are sorting in acsending order.

[@guapo6985]

Dude thank you!

[@slimanemesbah8500]

awsome lesson

[@ankushpatel9536]

The space complexity for this version is O(nlogn) - I believe you can do it better by passing around bounds for left and partitions and use an auxiliary array. This would be O(n) in space.

[@gursimrankaur8655]

you're a saviour. thank you

[@alrightytighty1572]

Hopefully someone can answer for me, why is mergesort faster? What it seems like is dividing elements and then making an entirely new array that had to be sorted anyways

[@ethanrose4925]

this was firee homie

[@100subsciberswithnovideos4]

Play this in 0.25 He sounds drunk lol

[@franciscoabusleme9085]

.5 is even better

[@chuck_norris]

ok so in the 2nd part after the split up your Algorythm magically puts the elements into the right order??