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

=========================================
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

[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)

[sarikarai]

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

[rishabhmohan_]

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

[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] <= second[j] favours left elements over the right ones thus maintaining their relative positions as it was in original array. There are many cases where l<=r makes algorithms stable

[anjalithakur_]

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

[ketaraod]

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

[mdmozammilraza]

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

[ujwalapatil]

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

[RashidIqubal-wwds]

It is briliiant from Kunal, You are the lengendary of DSA. Keep it up bro. God bless you.

[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.

[-farhaanali]

Exceptional, this guy deserves the best award for dsa

[akashkorachagaon]

Words are not enough to appreciate your way of teaching.

[sammedsankonatti]

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.

[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!

[Victor-wywj]

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.

[Anush_]

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 !

[Tomharry]

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

[sarthaksinha]

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);

}

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<m && k<e){
if(arr[j]<arr[k]){
ans[i]=arr[j];
j++;
}
else{
ans[i]=arr[k];
k++;
}
i++;
}
while(j<m){
ans[i]=arr[j];
i++;
j++;
}
while(k<e){
ans[i]=arr[k];
i++;
k++;
}
for(i=0;i<e-s;i++){
arr[i+s]=ans[i];
}
return;
}
}

[Helly_Patel]

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

[desihiphop]

Just a single word for you " Legendary "