Merge Sort In Python Explained (With Example And Code)

Merge Sort is an efficient sorting algorithm with O(nlogn) running time. In this video I show you a quick example and how to implement this algotrithm in Python step by step.
This video is part of the basic algorithms in Python playlist. The goal is to get an understanding of basic computer science algorithms and their implementation in Python.
For more coding videos subscribe to my youtube channel.

[@Eduardo_C]

Probably the best videos I have seen on these basic algorithms on KZbin. Keep up the awesome work! have learned so much from your videos!

[@t-distributedkid3825]

Probably the best merge sort video on youtube.... Lot of people just confuse on this topic due to lack of clarity... even the experieenced ones

[@a.m.4154]

The algorithm in code form is not intuitive or trivial at all.

[@anall3l3]

Clear, concise, thorough and simple algorithm. Finally understood this, thank you for your great explanation!

[@EagerEggplant]

Been on YT for too long looking for exactly this, a simple implementation. Brilliant.

[@sucraloss]

Wonderful explanation, I really like how you describe WHY you are doing things at each step. Many people create tutorial videos where they simply say "okay and now we do this to get it to compare how we want to" and don't say why they do it that way.

[@tusharnaagar2587]

read a comment that this is the best video on youtube for merge sort and i would like to say indeed it is the best

[@arnavverma2135]

This was amazing, keep it up...

[@FelixTechTips]

Thanks :)

[@RootUser-lg1qh]

Its my first algorithm in my life and I am finally able to code it. Thank you for your help.

[@waaaaaaaayyyyyynnnee]

This is an awesome video! I am doing the algorithms module on Khan Academy. I understood what i was suppose to do fairly easily. Khan Academy's challenge is in JS but was not understandable. I skipped through to the code example part and you explained this perfectly. I understood exactly why you were doing each line of code instantly. Putting this into practice may be a little harder but now i have a code example which is thoroughly commented in my own words to help me solve future problems using merge sort THANK YOU

[@Kamil-rf5qn]

Hats off to you for explaining everything step by step, even the basic things like colon, every index. I'm a beginner with 3 weeks into python and i started my second course on FreeCodeCamp that's an interactive one with a lot harder projects than i ever done. This is my second recursion project, their variable naming was way too long and i was being overwhelmed with very long variable names. My code from project looks identical to yours and yet yours is so concise and easy to read. Recursion is still something that i'm struggling with, but i feel like this video got me closer to understanding it. Thank you!

[@zakariaryanmechkak3761]

Much better than the million videos out there just talking rubbish

[@user-oz4ts5mv5h]

The most clearly explained one. Great job! Thanks!

[@mohammedhrima1654]

thank you so much, You saved me, I tried to implement merge sort with C, but most of C tutorials make it complicated

[@ozzy4738]

This is really simple and elegant. I wish I found this video before battling with merge sort - Thanks

[@julian7934]

You explained this in such an easy way compared to my uni professor lol. I couldn't thank you enough for these vids!

[@shwetarajapure8830]

explanied so nicely ...understood after watching this vedio only.. mission accomplished!!

[@olafschlammbeutel]

Exactly what I need right now

[@TonyBaloney-c4k]

Great explanation. Remember to add the base case when len(arr)

[@ManuelGozzi]

Very well explained. My algorithms class was terrible lol.

[@moussadiakhate9022]

thank you so much this is what I call an explanation going straight forward to the point with all the important details this is a worth millions views

[@rhodabaruch4]

Thank you! This was a great in-place solution. I would love to see you walk through a non-in-place solution.

[@RoMAndrix]

Nice video Felix! I'm subscribed now. Keep doing tutorials because you're well-structured in explanation. Thank you!

[@aj_hari_7]

Best videos should reach more people. KZbin should show this kind of videos in recommendations. Highly recommended. Superb Explanation.

[@shivenmehru1571]

Great explanation with a simple and clean code example. Appreciate the help!

[@mythbuster4315]

excellent tutorial! right before my exam!

[@VladislavRashkov-e6w]

Fantastic! Thank you so much for the detailed explanation!

[@DungNgo-lw5lf]

finally understand, best explanation

[@jaganchowhaan9648]

This is the best explanation, I ever found on sorting . Thankyou sir!!

[@Eddie4k]

Bro u r amazing at explaining these! Best so far that I have found.

[@TheKorkahn]

I love sorting numbers! Thank you for the great tutorial

[@yiqiongxiao5255]

you did an absolutely amazing job on explaining merge sort! im glad that i found ur vid!

[@DanielSmith-uj7rr]

Hey There! Thank you very much for explaining this algorithm. You made it so easy to understand. I appreciate it. Thank you!

[@GermansLikeBeer]

Great video, thanks! It really helped me understand it. The way of splitting the lists was great, I hadn't thought of that Grüße

[@kieseatic9983]

The explanation was so clean and easy to understand... Thank you 😄

[@venkatabora1459]

Thanks for the clear explanation.But i have few questions. When we are calling the merged array(left_arr) function if my array is of length 1 for example. My code checks for the condition whether the length of my array is greater than 1 or not ie..if(len(arr)>1 and it will fail. When will it go to the first while conditions. Ex: 2,6,5,1,7,4,3 and my left_list=2 and right_lst=6 and now it will run array(left_arr) ie array(2) the condition is not satisfied here since my array length is equal to 1 so it will not go inside the loop right? Correct me if i am wrong since i am new to programming

[@surajmane9573]

This is when the recursion will stop with the list values of 2 and 6 and the lines of code after the recursive calls will be executed.

[@SanjuKumar-hk8yy]

Well done, dude your explanation is very clear I understand your explanation. Keep upload more video on DSA. 🤘🤘please

[@Ansarieng]

yeah really its very simple to understand the concept thanks dude for me before reaching to this video i think that merge sort is very hard to understand but when i saw this video i can say its very very simple thank you so much dude😊😊

[@lena-ck9wz]

i really like your videos

[@maxfrischdev]

Great explantion! Toll gemacht! 🙂 Danke Felix

[@alexrubio9507]

Great explanation and amazing presentation also! Thank you so much for sharing the knowledge!

[@Strydomlisa]

Excellent explanation of the code. Super easy to understand the concept this way, thank you.

[@ej6552]

So informative! Big up from jp🇯🇵

[@LukeAvedon]

The best video of all the videos!

[@son0funiverse]

You are awesome for teaching like this. Thank you a lot

[@kostekukowski4383]

that was awsome, you've helped me so much

[@osyman782]

Why does the function have no return

[@yamanarslanca4337]

Thanks for the video. However, I don't understand couple of things: 1) how come the code ever get to the line which starts with # merge comment if it is always sending array to the recursion in the case of len(array)>1 and if that condition is not satisfied it just returns the array (actually not because there is no return) so #merged comment and the rest of the code is never going to be executed. 2) Also, as I mentioned in the parantheses before, it returns "None" if I apply this code and if I add the return command (return array) at the end of the function, it gives wrong answer in which the array is not sorted correctly.

[@gabrielvictorrusso5931]

I have the same doubts! Did you sort them out?

[@MahlakaSami]

@@gabrielvictorrusso5931 did you try it?

[@gabrielvictorrusso5931]

Yes, I did, I know it works wonderfully, but I need help to understsnd whats happening, otherwise I’m just learning code recipes

[@folakeaiyetigbo4109]

@@MahlakaSami Same issues.

[@paulster185]

You're correct that the code only enters the merge section (# merge comment) when the length of the array is greater than 1, and it recursively calls merge_sort on the left and right halves of the array. However, the merge section is executed during the backtracking phase of the recursive calls. When the recursive calls start to return, they bring back smaller sorted subarrays. The merge section is responsible for combining these smaller sorted subarrays into a larger sorted array. So, the merge section is indeed executed during the recursive backtracking phase, not during the initial recursive calls. This is why the code is able to sort the array even though it might not seem immediately obvious. Regarding the issue with returning "None": In the provided code, the sorting is achieved by directly modifying the input array arr. Instead of returning the array, the sorting is done in-place, and the final sorted array is available directly in the arr variable. The original code sorts the array in-place, so there's no need to add a return statement at the end of the function. I hope this explanation helps :)

[@charliewebb7244]

perfect video. 10/10

[@ahmet8266]

thank you, I finally understood the merging step.

[@santiagolicea3814]

You explain things so well, thank you!!!

[@Yoo_broo_Jr]

Sirrrr wonderfully explained. just loved it.

[@hicham_baydoun]

in this code there is an issue where u should put a base case before the while loop if len(l1)

[@samuell77799]

Thanks, the explanation helped me a lot.

[@vihangatharushan4477]

actually this is very simple and wow explanation

[@luvlifk]

very nicely explained merge sort.

[@ligrt2426]

great video with details and simplicity, thank you!

[@smesysaltyisyno]

You've done more for mankind then democracy ever has.

[@atheeshrathnaweera]

Great explanation. Thanks.

[@darcash1738]

Awesome explanation, but based on how you implement it, the left side should be smaller in the example you give: Len = 7, 7//2 = 3. 0:3 captures the actual range of 0 thru 2, or the first 3 elements

[@bodalajahnavi6272]

Very Easy to learn. Thanks

[@NHCSKIRAN]

Was very helpful in the last minute

[@qaipak1]

so this is why you Germans are so good at engineering. such a thorough explanation!

[@rogueceska]

best explanation yet thanks.

[@mohsinkhattak2840]

hey felix i'm abit confused regarding the last two while loops in which we are simply adding the remaining elements of either of the array if there are! how are we checking those remaining values for comparison?

[@varunsrini7461]

This is the case where all the elements in the other array have already been added to the sorted array. If your left array is [1,2,4,5] and your right array is [2,3,1828,183885], then by the time you reach 1828 in the right array, all the elements in the left array will have already been sorted in the main array, so you can just add the last 2 elements of the right array without worrying about comparisons. Hope that helps :)

[@sudhakartripathi3879]

can u make count inversion video pls .........this is very nice explanation

[@lajoskicsi6910]

Thank you, this was a super useful video!

[@amanaggarwal4061]

Great Video please make data structure and algorithms full series playlist

[@shaiksalman9010]

love ur lucid explanation❤❤❤❤❤

[@IslamSoliman_Sci]

I Loved It So Much.. Good Luck

[@ayushshubhankar858]

Thanks for these videos felix!!

[@miyurux]

Great video bro... keep it up👌🤙

[@Nick-gs4em]

Absolutely amazing. Thank you, thank you, thank you.

[@al-washisarkerturan8913]

Is O(n) the time complexity of this code or is it O(nlogn)?

[@vm7240]

thank you! very easy to understand explanation

[@pranjalsrivastava4265]

brilliant explanation, Hats off

[@eniyan4265]

Y u don't show the results in screen

[@egipebriyawan1455]

in minute 6 you said seven ? its thats means 5 ? yes or no?

[@abufaya4155]

Wow man ur underrated!!

[@ConnieTriplett]

shouldn't the first while loop conditional read "if left_arr[i]

[@tljstewart]

Simply Beautiful, thank you.

[@logofios]

Cool realization!

[@azlanikram9393]

how is array of size one already sorted, I can't understand that part

[@pattytheratty]

well how can it be unsorted, for example a list of one: [25] cant be out of order because theres only one element

[@ZahZah571]

Very clear! Thank you very much

[@lookaway8496]

thanks for this great explanation

[@bulisharma1138]

such a nice explanation thankyou

[@python_knooobb]

Hi Team, in the line 2, it is giving me runtime error, stating mximum depth recursion comparison

[@aotforlife1346]

Since you are calling a linear function (len()) every time. Doesn't that worsen the overall runtime? I tried the same program on my computer with a list of length 100 million. It took around 1 minute when it should have been alot faster for a n log n function

[@peachinvibes5858]

you forgot to implement return (arr). But your video was on point

[@sanooosai]

thank you

[@egemen_ozturk]

I have a question about your method. Is this fully recursive? Seems like only the first part.

[@cachaceirosdohawai3070]

Great video keep it up

[@Code4You1]

Very easy to understand thx!

[@harvzgames9622]

How would I do with this names and scores, like a highscore table where it will put highest score at the top but if 2 players have the same score it goes alphabetical

[@redeemuser]

Neat clean and concise

[@СофіяСампара]

This code isn't working. But you have helped me to better understand this algorithm.

[@SusanAmberBruce]

Is it pythonic? Or is it code from an old C program adapted to run in python? Clearly, the code demonstrates how the merge sort works.

[@riyazshaik864]

awesome explanation

[@latest_news_stories]

Awesome tutorial

[@efrainm4649]

I'm not understanding. Why are the last two loops necessary??

[@baochu8082]

Hi, can someone please explain to me the recursion part? I can only vaguely understand how recursion works in this problem. Thank you