Merge Sort Using Recursion (Theory + Complexity + Code)

In this video, we cover the merge sort algorithm. Including the theory, code implementation using recursion, space and time complexity analysis, along with the in-place sorting approach.
Take part in the learning in public initiative! Share your learnings on LinkedIn and Twitter with #DSAwithKunal & don't forget to tag us!
👉 Resources
- Join Replit: join.replit.com/kunal-kushwaha
- Complete Java DSA playlist: • Java + DSA + Interview...
- Code, Assignments, & Notes: github.com/kunal-kushwaha/DSA...
➡️ Connect with me: kunalkushwaha.com
=========================================
Timestamps:
00:00 Introduction
00:31 Merge Sort
03:16 Steps for Merge Sort
06:58 E1 : Recursive Merge Sort
22:18 Explanation of E1
25:31 Time Complexity
29:01 Space Complexity
29:37 Solving Complexity using Akra-Bazzi Formula
33:06 In-place Merge Sort
44:14 Code for in-place Approach
49:34 Outro
#sorting #placement #dsa #interviews

[@mdmozammilraza3215]

Best explanation than other KZbinrs. Hope you will upload videos as like that will help us in competition programming.

[@tasneemsf3421]

Which language is he using ??

[@prajwalm.s7976]

@@tasneemsf3421 Java

[@mdhaidarparwez968]

Inplace merge sort is incorrect,he is still using extra array,how he can say this is inplace,if you don't know inplace sorting ,why you teach wrong concept?

[@futuremaster8204]

@@mdhaidarparwez968 exactly

[@sarikarai9241]

Only one request is... Please Do complete this playlist ( in whatever tym) just don't leave in between. It's the best course ever.

[@KunalKushwaha]

I will complete

[@SunnyGupta00]

@@KunalKushwaha when?

[@vdas1335]

@@SunnyGupta00in October

[@SunnyGupta00]

@@vdas1335 not possible

[@dark_techyy]

dont worry nhi chhodega vo...he is lion 🦁 😅

[@rishabhmohan_]

Undoubtedly...best ever course for DSA on KZbin. Thanks Kunal, for giving this level of content for free. ❤️

[@anjalithakur_12]

Probably you're the best teacher in my whole life that I am able to understand everything without asking much questions. Simply you're the best

[@ujwalapatil650]

Words are limited to appreciate this bootcamp!! Nice bro Thanks

[@Helly_Patel]

Thanks for teaching us like no one did till now!! One small request, please make lectures on dynamic programming as well!!

[@MIHIRHUNDIWALA]

For those who are wondering about stability, the version of mergesort implemented in the video is unstable, but a simple tweak can make it stable changing the condition to first[i]

[@_DashingAdi_]

What's a stable algorithm?

[@capedbaldy123]

​@@_DashingAdi_ suppose there are multiple same element/number in array, their positions will be preserved as it is.. without changing it... suppose [2(1st), 2(2nd), 2(3rd)] their positions will be preserved as it is...

[@satnamsingh3801]

Exceptional quality of teaching and content delivering.

[@KartiKKaushiKYt]

I don't know how to explain this but when I am stuck on a uni task, I get a weird sensation of safety watching your videos as I know if I understand your video thoroughly, I will get the answer. Thanks.

[@ketara1234od]

It's the BEST course ever , i recommend everyone to watch it

[@akashchoudhary681]

Thanks for this video. Now I don't have any confusion in Recursion.

[@kratikesh]

The Best Explanation of MergeSort !

[@alonbrim]

Great video! Thank you very much Kunal!

[@jamespeterson7824]

Very good and in depth explanation of the algorithm... Good Work 🙂

[@tanishkumar5827]

forever grateful to you kunal!!!

[@TheRaf66]

Best explanation ever. Thank you

[@sadhananath1807]

one of the finest in explaining things 👌

[@Victor-wy1wj]

The explanation is on the next level. I finished the second year of college of Technology and Informatics and those topics were hard and weird to me but now while i'm in vacation i decided to give it a second chance , to try to understand them finally because it's a really important topic. Thank you so much Kunal for your explanation and that all of this is free.

[@saujanyajaiswal3576]

Hi Kunal, Thanks for uploading the video . Uploaded video are helpful and explanatory videos for fresher and experience folks. I have a suggestion for you. Please upload a video for Thread class ,Multithreading, thread pool etc..

[@49-farhaanali86]

Exceptional,this guy deserves the best award for dsa

[@sammedsankonatti9642]

Even after watching so many videos on merge sort i was in confusion, but this video alone did wonderful job to clear so many or all the doubts🤩, Thank you and keep going.

[@ashwithchandra2622]

Wohhhhhhh explained really very well it was very deep caught all the concept....Thank you so much...!!!!

[@desihiphop4998]

Just a single word for you " Legendary " !!!!!!!

[@anush6266]

I saw a dozen of merge sort videos but did not understand. Finally, your explanation went straight through my head and not a bouncer :) Thanks a lot for this amazing video !

[@rjesh2062]

Kunal is great but imo his explanation is spoon feeding I was not able to think on my own after his tutorials...Try Aditya verma videos after conpleting topics he helped me alot with thinking approach

[@CineSavvySoul]

@@rjesh2062 its not like spoon feeding. but we can say that his approach is addictive and even better than others.

[@varshakowdi7305]

Amazing Videos, I have been learning a lot from these! Please also explain Trees, Graphs & DP.

[@luisquiroz8586]

@Kunal Kushwaha In the sort in place code your base condition is if (end - start == 1). why is this the base I thought you wanted to return when you only have one element. but in your case you will have 2 elements because if end is 1 and start is 0 => 1-0 = 1 but that's 2 elements 0 and 1 so why is that base?

[@charname2077]

Yeah he made a mistake there. This code will fail for an array like [2, 1]

[@sufiserious798]

The key to understanding the reason is at the start of the code, where the function is called for the first time. There Kunal passed '0' as start and 'arr.length' ( 1 so the algo will proceed ahead to next call In the next call we will have arrays containing only a single element for example {2} Then start is 0, end is arr.length that is '1' , not '0'. Now, our array contains only 1 element and (end - start) will be (1 - 0) which is equal to 1!! Thus, the single element arr will be returned directly above !

[@NareshNaresh-cl8rn]

Kunal alpha character explanation I doesn't think anyone who can teach like him

[@girirajtomar519]

Amazing lecture brother.

[@the_ranjit_kumar_nayak]

Eagerly wait for it kunal

[@akashchoudhary681]

I can say proudly that this is the best DSA course on youtube. Thanks Kunal

[@komalswami2437]

best DSA course ever💯💯💯

[@vanshsharma2486]

great video bro, thank you so much!!

[@akshaykumar-wd8jc]

Great explanation

[@youmadvids]

Your vids are awesome man. This is exactly how algorithms should be taught. I've got my final interview with Microsoft tomorrow, wish me luck!

[@KunalKushwaha]

Best of luck!

[@sofiyarao815]

were u able to crack it ?

[@youmadvids]

@@sofiyarao815 I got 4/5 working solutions, unfortunately didn't get the job :(( but its all good practice!

[@nikhilchauhan3506]

@@youmadvids now whats your current status man

[@suryaer3369]

Please complete this series boss , it gives me panic once you give some gap in between 😄😬

[@dinbandhusharma4568]

Thanks for this amazing explanation I really like it 🤗❤‍🔥🔥👍🏻

[@hhhhhhhhh963]

Hey Kunal, This is the best course I have came across. But I just wanted to ask you when will the course finish?

[@samarthdhawan2229]

At 29:15 you said there are N elements in the stack memory but there should be atmost logN elements in the stack memory as it is the height of the recursive tree......Btw thanks for this amazing DSA series it really helps me a lot

[@abhijitmanna4524]

O(log n): If you will declare the intermediate array in heap. O(n): If your intermediate array is stored in stack.

[@sureshkannan6313]

Thank for the lecture. My support through subscribed already 😊

[@antoniokhan9367]

Kunal on Fire!

[@prakashyemineni5199]

Debugging by my self helps me a lot 👌.

[@satwikvarma2804]

great work mate

[@asainikhith569]

Hi Kunal pls also do the videos on applitude and reasoning it will help ful..

[@abhhack]

37:45 There is Not arr,m,end this is arr,m+1,end

[@Vedsingh.]

Brooo suppper👌👌👌👌👌👌👌

[@zuojimmy1198]

Great video! I have one question: for the mergeInPlace function, it created a new array int[] mix = new int[e - s]; --> so is it still considered in place?

[@7billon680]

Awesome bro thanks for dsa bootcamp...❤️

[@sofiyarao815]

Kunal in every video -> recursively stating = Already explained in prev videos please watch ...

[@_Afreena]

Hey kunal !!.. When ur going to complete entire lectures of DSA boot camp? Needed much : )

[@aniketpandey62]

Hey Kunal, you missed some conditions in merge sort code in function merge(), while(k < first.length + second.length -1 && i

[@dineshmadduru7043]

Thank You :)

[@badalsharma393]

sir their is problem in printing the arrey in main class , because the syntex you give in github and the syntex in your video is different .

[@suyashkumar8840]

Love Babbar be like jldi jldi one shot recursion bna ke bacho ko geekforgeeks ke course bech deta hu 😂😂

[@diveshkumar8025]

Love babbar Only Makes us fool.

[@suyashkumar8840]

@@diveshkumar8025 definitely

[@dillirajtimalsina]

haha

[@YouCodeRK]

Hey Kunal, How your are using debugger in such a way that it is showing each and every step....is any extension installed or just using F5

[@YN__YN]

when e-s ==1 .. the array will be having 2 elements.. how that is working properly?

[@akshayyadavbtech2433]

thank you so much

[@jagadishrvjp4450]

My doubt is that the mid index is passed twice ( in left array, as well as in right array ), won't this repeat the number in the final array? I was wondering whether the right array's mid should be passed as mid+1 or something like that?? Anybody please clear my doubt!

[@jagadishrvjp4450]

Found it: Basically, when you copy the range of array, the last element is exclusive (i.e) when you pass Arrays.copyOfRange(arr, 0, mid); // mid is excluded! and when you pass Arrays.copyOfRange(arr, mid, arr.length) // mid gets included here, and arr.length = 5, so 5th index is excluded which doesn't exist as the index starts from 0, so last element is basically index 4, which is also covered !

[@madhusudhanreddychencharap4881]

can you explain these case with the inplace method@@jagadishrvjp4450

[@_DashingAdi_]

​@@jagadishrvjp4450But even while using InPlace sorting (where he did not use .CopyOfRange) he still passed mid two times.

[@ssu1782]

everything is easy with ur explanation except the math part for me coz no clg need to learn calcu! great vid btw

[@Saurav25811]

pretty cool stuff

[@davinder95]

thankyou brother

[@venkatavarunlinga1081]

thank youuu;)

[@vasujhawar.6987]

long time, missed you.💗💗

[@KunalKushwaha]

Welcome back!

[@deepankarmishra0823]

Bro when will be this dsa playlist will be completed?

[@sw9554]

How to get that Java implementation thing in intellej - ( where you clicked on copyOfRange)

[@venutalla5932]

best sir in world

[@satwikvarma2804]

Which one should we use if asked in an interview inplace or normal mergesort

[@KunalKushwaha]

first normal then inplace

[@satwikvarma2804]

@@KunalKushwaha thanks mate

[@sarthaksinha5798]

Merge sort by changing pointers of index value: import java.util.*; public class Main { public static void main(String[] args) { Scanner s=new Scanner(System.in); int arr[]={5,4,3,2,1}; merge(arr,0,arr.length); System.out.println(Arrays.toString(arr)); } public static void merge(int arr[],int s, int e){ if(e-s==1){ return; } int m=(s+e)/2; merge(arr,s,m); merge(arr,m,e); int ans[]=new int[e-s]; int i=0,j=s,k=m; while(j

[@Blu_Dragon6206]

while copying the answer of mix in original array why do we have to take arr[i+s]?

[@clownop2201]

Best video

[@mohamedirshaathm32123]

hey kunal when u say "I am not going to teach u these easy stuff again" we actually get a recap of your previous concepts.

[@poorpanda9033]

Coming here after watching your video on Recursion ( makes it so easy to understand ) 😂

[@GoodBoy_._]

for those who found time Complexity difficult to understand I think I can Help --> 1.Total no .of recursion calls = logN 2. No of numbers to merge in each recursion calls = N Time COmplexity =O(N*logN)

[@user-xx5nv6kq6m]

Why didn't you put 'return' while creating left and right arrays? There must be return when function has a datatype right?

[@piyushsukhwani-qm2pn]

what about comparisons made in copying of array in method "copyofrange"????

[@rudram4534]

still watching consistently 😀😀😀 😀😀

[@dickharry910]

Recursion and how recursion worked lay hid in night; God said, "Let Kunal be", and there was light!

[@rahuldatta1382]

east and west,kunal is best

[@aryanverma1233]

How after dividing arrays in halfs those halfs are getting sorted?

[@plutomessi21]

Same doubt dude😭

[@jhunecamatura4926]

same same hahaha' @@plutomessi21

[@user-pp2jn7pm6g]

we divide arrays until its size become 1. when we merge both arrays of size 1 then it likes comparing two numbers.

[@venkataramanabonu8338]

tq sir

[@varuns3763]

u r op kunal

[@itshari5489]

Video 30 Completed!

[@chinmaythaokar3560]

nice

[@bikramshah8506]

I am getting index out of bound exceptions while running the code in my compiller

[@sumitraj5529]

Please make a video on Graph

[@alviahmed7388]

When copying elements of mix[ ] to our arr, why are we saying arr[s + l]? Can't we say arr[l] = mix[l]?

[@_DashingAdi_]

Because the start varies for each recursion call. If we're in the last call the start can be somewhere like index->4 so if we use arr[l] the elements will get copied from 0 instead of the particular start index of that Recursion call. Using arr[l] will get the elements copied from 0 at all time regardless of which call hence it's wrong. When we use arr[s+l] we will copy the mix of that particular recursion call at the start of the array of that recursion call.

[@amanagrawal2570]

Can you please complete the whole bootcamp.

[@mayank3411]

Inplace sort smjh nhi aaya merge kaise hua usme?

[@deepakkumar9834]

Number of comparison will not increase more then n- 1 ??

[@roopesh668]

Why N-1 comparisons are required to merge arrays. Go anyone explain this

[@nagar.gourang]

Finally wait is over ❤️

[@divyaraichura1923]

what is the comparisons for merging N or N-1, i am confused, in complexity we write N logN and in relation you wrote 2T(N/2) + N-1

[@abhijitmanna4524]

that is recurrence equation not time complexity

[@anukritisingh4479]

pls upload dp series video soon

[@shreya6676]

Can you please tell Why you have not taught heap sort

[@virat7800]

maja agya 😀😀

[@abhijitmanna4524]

This time complicated mergeSort into mix etc it should have been taught in simple method.

[@shubhambansal8794]

why do we use Sorting algorithms when we have a direct method which is Arrays.sort() 🙄 ?

[@KunalKushwaha]

lmao, .sort() also uses these methods. its not magic.

[@kunalchauhan5294]

Not gonna to Lie You are Really A King 👑 Not just like this dude You blew My mind You are fantastic my Dude You just made everything so Simple

[@rohitmondal3438]

I've used the same program as of you of in-place algorithm, then why it's giving wrong answer ??

[@_DashingAdi_]

Because the algorithm is full of bugs

[@CineSavvySoul]

first time kunal sir gets confused🤭🤫

[@mrrishiraj88]

👍👍👍

[@bibhavkumarsah7650]

All the things kunal explained was so much clear but I have a doubt about why is he using arr.length and not arr.length-1 in the in place merge sort part?

[@immortal4412]

same.. have you figured it out?

[@wegojim732]

@@immortal4412 I know it's late, but in JAVA, arr.length returns total number of elements(1 indexed), not the SIZE of the array(0 indexed), unlike C++, example: {1,2,3,4,5} n = 5, but 5 is the 4th element.

[@sufiserious798]

@@wegojim732 arrays are 0-indexed in C++ too, that is not the reason for using arr.length