Merge Sort | Code and Explanation | C++ Course - 19.1

Complete C++ Placement Course (Data Structures+Algorithm) : • C++ Full Course | C++...
Telegram: t.me/apnikaksh...
Instagram: / dhattarwalaman
Notes of this Lecture:drive.google.c...

[@sohebshaikh3344]

accha explanation tha bs thoda code dry run kr k batate tho zyada accha hota

[@akshaykumar192]

Kahe ka acha kuch samaj ni aata 😢

[@achabacha3809]

​@@akshaykumar192 😅😅😅😅

[@eros4082]

Code is giving undesired output if array elements are other than descending order. I have checked many testcases.

[@vindhyakumar3434]

bro after seeing your comment i realised the same mistake i made , maybe in int main you forgot to put mergesort(arr,0,length-1) and instead wrote mergesort(arr,0,length)

[@prabhatjha2522]

@@vindhyakumar3434 then also It didn't work

[@tywarinabin]

It is difficult topic but this lecture of 15 minutes make it easier and make program just in 10 minutes. Thanks Apna College Team and Aman bhaiya.

[@turbo4free631]

is this course for beginner.....

[@amritpoudel6929]

@@turbo4free631 NO BIG NO

[@mrpandey7312]

thanks to all who created this free of cost course

[@nithinshukla4679]

fr i couldnt understand anything after didi stopped teaching😂🤣🤣🤣

[@pritishpattnaik4674]

instead of using 2 more while loops in merge( ) , u can simply just change the && with || , so..we do not need those extra while loops.

[@sourabhchoudhary7289]

I also thought so does it worked??

[@amanns7080]

No it won't work, might give a segmentation fault/ wrong answer as you are accessing element of an array outside its bounds. Suppose, i has reached n1 but j hasn't reached n2, by replacing "and" with "or" in while loop, you would still enter the loop, but this time you would be checking a[n1] with b[j], a[n1] might contain garbage value. Same case if j reaches n2 first, b[n2] contains garbage value. Hope this clears your doubt.

[@shreyasingh4680]

no we can't do that because we would have 0 element in either array so we can't compare

[@code-a-mania4100]

For Time comple. We get fractional part and n so it is simple it is logn*n

[@technicalknowledge9080]

Bhaiya this code is working correctly only for the input (5,4,3,2,1) while we are changing this input then this code is not giving the correct output so please look into this matter. and please highlight this comment so that bhaiya can read this comment Thank you

[@rishankbhatnagar6560]

mera bhi output nahi aa raha hai

[@divyangbhamat1228]

Yes same problem anyone found solution so please help

[@sohammukherjee_2193]

Bro which part sorts the arrays of size n1 and n2???

[@irshadali-xx1ms]

#include #include using namespace std; void merge(int arr[],int l,int mid,int r) { int n1=mid-l+1; int n2=r-mid; int a[n1]; int b[n2]; for (int i = 0; i < n1; i++){ a[i]=arr[l+i]; } for ( int i = 0; i < n2; i++){ b[i]=arr[mid+1+i]; } int i=0; int j=0; int k=l; while (i

[@technicalknowledge9080]

@@irshadali-xx1ms thank you bhai 😀😀

[@vaibhav7453]

Take input from user

[@shaktirajsinhzala4588]

merge is done with only one extra array. it is not necessary to take 2 extra arrays and then merge.

[@nikunjjain2382]

Yes ,by using two pointer

[@sourabhchoudhary7289]

we are using two arrays of size n1 and n2 that is n1+n2=n. so basically we are using O(n) extra space that is equal to one array of size n.

[@MohammadKhan-ld1xt]

how?

[@yashvats824]

@@MohammadKhan-ld1xt #include using namespace std; void merge(int a[],int s,int m,int e) { int temp[e-s+1]; int p1=s; int p2=m+1; for (int i=0;im) { temp[i]=a[p2]; p2++; } else if (p2>e) { temp[i]=a[p1]; p1++; } else if (a[p1]>n; int arr[n]; for (int i=0;i>arr[i]; merge_sort(arr,0,n-1); for (int i=0;i

[@sjr2001]

In the int main func when we write mergesort func then copy of arr should be sent . Then how does the sorted array got print by for loop not original array ???

[@govindjangra600]

can anyone tell the problem that i faced in running the same code in the video my output is 5 2 5 5 5

[@sleepypanda7172]

her voice!!! too sweet! Great explanation!

[@sakshidurve1211]

merge function is not only to to merge 2 arrays, its is also to sort and merge

[@sohammukherjee_2193]

But in which portion is the sorting occuring???

[@cswd428-yaswanth3]

@@sohammukherjee_2193 in the merge fn

[@UIEC_MANESH_RAM-tb1hb]

your absolutely right and maybe didi missed it

[@AmanKumar-nb4oh]

Yeah u can say like that while merging we sort them first

[@rohitsaini7427]

Isn't the L pointer going to be zero and in what case it will be non zero?

[@aswinbarath]

🔥🔥🔥Verithanam🔥🔥🔥

[@anantsinghal3180]

Please upload web development course...🙏🏻🙏🏻

[@nikunjjain5212]

@Nikunj Manhas thanks Nikunj 😂

[@zackcarl7861]

What does( mid-l+1 ) mean how can I substrate l from mid

[@himanshuwarkade4318]

As l always starts from 0. Suppose the value of Mid is 3 so "3-0+1" is equal to 4 which should be the size of first part of the array.

[@AG-kw1rb]

Bhaiya Please upload the NOTES OF LECTURE 31 - Strings in c++

[@aadityasharma6855]

Its 13

[@AG-kw1rb]

@@aadityasharma6855 Its Lecture 31

[@AG-kw1rb]

@@saimadhumita2144 yeah

[@AG-kw1rb]

Thank you Aman Bhaiya and Apna College team as now the Notes of Stings in C++ are uploaded

[@cmcatholic1798]

Mergesort() function seems bit odd for me, since there is no returning statement🤔. I think it should return 0 at end

[@zubinshah4589]

its a void function bro

[@praveenawesome2182]

well yes but actually no !! Firstly mergesort is a void function so it should not return anything but let's say if it wasn't a void function and something happened in the function but it doesn't return anything,in that case, no one knows for sure what will happen. The program may or may not run i.e it can result in a crash so to avoid that situation we always have return statements even after giving a return in a conditional statement inside a function.

[@praveenawesome2182]

ps: I am not sure if the above claim made by me is totally correct and maybe there is good logic behind it, suggestions will be appreciated.

[@gauravupreti9340]

there are two ways in which a function frame can be destroyed, either if return statement is encountered or if nothing is left in function. Try to think with a stack diagram. Hope it will help.

[@harshdeep7312]

@@praveenawesome2182 definitely u r correct i encounter many time no output wthout return statement bt after return statement program gives correct output

[@AbdUllah-m2j3j]

Only one of you can teach me correctly so proud you

[@shubhamkale735]

Documentation of our program is very important thing because it reminds us the logic behind program make sure everyone will write reason after each code using commenting

[@joebale9670]

ji sir jaisa aap kahen😶

[@AmanTheDisciple]

Awesome video, thanks for the easy explanation! :)

[@maheriyajatinbharatbhai3538]

thanks for this amazing playlist!

[@vatsalpoddar6660]

In the Merge function, why did we initialize k with L and not 0

[@artirani3806]

It's special for me because it is on Apna College Video.....first time ever😇1 comment, 1st like😄

[@ankurmishra1175]

kzbin.info/www/bejne/aJyaoYZvrLyDiqs

[@RudranshSharma]

Backtracking ke baad toh kuch samajh nhi aa raha!! What to do?? Ek baar poora course dekhlu aur uske baad phirse dekh lunga..... Yaa fir abhi poora concept clear karte huye chalu?

[@strokeadda01]

Bhai clear krta chal abhi se wrna pura dekhne tkk itna frustrate ho jaega ki kr nhi paega🤐

[@felizmonk5383]

Don't we have to take dynamic temp array in merge function. Why didn't you get errors?

[@VishalGupta-oh7mb]

space complexity ne allow kr dia On ko isl;ie

[@lakshtrivedi004]

Can we get backtracking part 2?

[@ishitabisaria6437]

Sir notes of this lecture??

[@rexstark5319]

Why do u not get errors, even if u declare size of arrays as variables at runtime

[@paramrajsinghchadha1957]

varies from compiler to compiler

[@dibyarupnath]

you need to declare and take input the variable, which you use as the size of the array, while declaring the array.

[@rishabarya1379]

THEY SKIP TO THE PART WHEN CODE IS RIGHT YOU CAN SEE IT FOR YOURSELF EXAMPLE THE VEDI THEY TYPE "mergeSort(arr,0,4);" BUT AFTER EXECUTION WHEN YOU CAREFULLY LOOK IT IS SUPPOSED TO BE " mergeSort(arr,0,5);"

[@sajankumarkar8237]

Just another way to merge. We can take a single array of size n instead of 2 of n1 and n2. What we do is we divide the original array by marking them with the pointers i,j(not the * pointers xD). We merge and store them in the temp array and at the end we store the values in the original array. void merge1(int a[], int l, int mid, int h)// low, mid, high { int i=l, j=mid+1, k=0, n=h-l+1; int temp[n]; while(i

[@adityagupta3870]

brother....can you explain me why the size of " n1=mid-l+1" array is taken? and in your problem also n=h-l+1?..please help I am confused

[@sajankumarkar8237]

​@@adityagupta3870 ok let's say the array we take has size 10. While calling the function the value passed to low is 0 and the value passed to high is n-1(cuz if size 10 means from 0 to 9), i.e. 9 in this case. Now in the function, n denotes the size of our array(specifically size of the part of the array corresponding to the merge but here i will explain for the entire array cuz its easier to understand that way). So n needs to be 10. now low=0 and high=9, so high-low=9-0=9. So we add 1. High-low+1=9-0+1=10.

[@adityagupta3870]

@@sajankumarkar8237 damn bro!!!.. Thanks!!!... Can I have your id or something ... So that we can start with dsa together?

[@samridhisaini6147]

explanation is just so clear

[@derekflix]

Kyo karna hai merge sort jab hum pehle hi Selection Sort, Bubble Sort aur Insertion Sort padh chuke hai ????

[@mansoorahmad5774]

Due to time Complexity. Most efficient sorting technique as compared to others.

[@vinayakjalan5696]

Didi iss lecture ke notes add kardo description box main .. Woh blank reh gaya hh

[@faizansaqeeb3390]

Amazing👍😍🤩

[@gourav7921]

Int n1 = mid - l + 1 Didi ne 8:24 par (mid - l )mein 1 kyo plus Kiya hai agar kisi Ko iska reason pta hai toh pls jrur btana

[@virendraverma5855]

Function Mergesort how it working samajh nahi aaya

[@imranimmu4714]

expecting better explanation for time complexity

[@SobhitPanda]

Sir, time complexity nahi samjh aai? Please elaborate, the procedure. Or please suggest some materials to practice from.

[@sachinbairi6353]

Are voh keh raha hai ki humne pehele n length ki array ko divide kiya half mai toh hum abb left array ko sort karne ko humko t(n/2)time lagega some for the right half of that array jab hum dono side ko plus karenge tab yee ayega -->>> i.e. t(n) = t(n/2)+t(n/2) = 2t(n/2) but hum divide karne ke baad merge bhi kar rahe hai toh usko humko merge karne ko linear time lagega i.e 'n' toh final recurrence relartion atta hai ki t(n) = 2 t(n/2) + n ...eq1 yee aaya hai for the first split jo humne kiya n ko n/2 mai but hum mergeSort mai we divide the input list of length n in half successively until there are n lists of size 1. so, if humko left or right half of the array ke liye recurrence relation chahiye toh follow same procedure but iss baar n half hai. replace n by n/2 in the eq 1

[@hrithikjaysingpure9623]

@@sachinbairi6353 thnx bro

[@shamshuddinshaikh4774]

@@sachinbairi6353 tumne toh bade acche se samjhaya bro

[@prafulraghorte6189]

I have copied same code word by word but My code isn't running 😒

[@aaravchaprana3381]

same here bro wont know what the problem is

[@sagarjain4128]

in void merge(int arr[ ], int l, int mid, int r). You said in arr[ ] we are getting to small size SORTED array. 1st array from l to mid. And 2nd array from mid+1 to r. And you said now we will make two temporary arrays. then merge them. KINDLY SOMEONE HELP 🙏🙏🙏🙏 But in the starting how this arr[ ] got SORTED small size arrays??

[@abhishakekumar3243]

we are using recursion here, merge() function will be called number of times for every separation after mergeSort() function, not only once. And two temporary arrays because we can't traverse and make changes in the same array at the same time.

[@lifeatovarun]

output is coming wrong what's the problem behind it. #include using namespace std; void merger(int a[],int l,int r ,int mid){ int n1=mid-l+1; int n2=r-mid; int b[n1]; int c[n2]; for(int i=0;i

[@animegod5295]

why is it showing expression must have a constant value while declaring temp array? pls help somebody

[@Special_moment_]

very good explanation . I really enjoyed.

[@rohandhale9766]

Best explaination Of Logic And TimeComplexity

[@pankaj.yadav1]

Ma'am bhut axa smjhati h

[@ManmohanBhardwaj-ft2hu]

Program is not working it show error in running in online gdb c++ compiler

[@krishnaanasurya3549]

Thx for Desi explanation , Ghusenge ghusenge...

[@goravkumar125]

Ma'am mergeSort sahe work nhe kar rahr hy mana bhut bhar check kiya hy liken program main kohe error nhe hy liken arr ko sorrt nhe kar raha hy

[@DALJEET20]

i have copied same code but my array is not sorting please help

[@developer0707]

getting output only when I give input as same you have given but whenever I change my input array sequence or give a sorted array as input code is not working

[@harshitnema4197]

For those who are having doubt in line of code where: n1 = mid-l+1; see initially we have given l = 0, r = 7 in the array of length 8. then we will get mid = (l+r)/2 as (7+0)/2 = 3; so n1 = mid - l +1; will be 3 - 0 + 1 = 4;

[@harshitnemaa]

If you guys have any doubt you can reply to this comment.

[@shubhammahakal1817]

Here, mid is pointer and n1 is length from 0 to 3 (0,1,2,3)

[@hemant-li1gp]

in mergeSort function we pass arr of main function by value, then how did this changed the array in main function

[@ashishbohare8864]

Love u didi 😘 bdiya pdhaya

[@nothing-ce6rs]

Mam u r keep saying pointer.. Is that pointer or index? Bcz pointer should have Asterix(*) sign

[@harshitrathi3077]

Aree Bro Pointer Doesn't Only Means That U have To Take a * Sign , Pointer also Means To Pointing something

[@nothing-ce6rs]

@@harshitrathi3077 acha

[@digvijaypatil2147]

the array was not dynamic then how it got sorted in main function? plz someone explain

[@khuramkhalid5396]

THANK YOU SO MUCH!!

[@PulkitMalhotra]

1no. Content 🔥

[@ansariafreen9594]

will merge sort work for odd no. elment in an array?

[@Emc-nt7lo]

Yes

[@sanyampandita5488]

CAN ANYONE PLEASE EXPLAIN WHAT IS THE ERROR IN THIS CODE: #include using namespace std; void merge(int arr[],int l,int mid,int r){ int n1= mid-l+1; int n2= r-mid; //temp arrays int a[n1]; int b[n2]; //array ke elements ko 2 temp arrays mein bhar rhe hai for (int i = 0; i < n1; i++) { a[i]=arr[l+i]; } for (int i = 0; i < n2; i++) { a[i]=arr[mid+1+i]; } //checing when putting the values backing in the k array int i=0; int j=0; int k=l; while(i

[@ritulmittal2651]

In merge function the second for loop should be b[i]=arr[mid+1+i] instead of a[i]

[@anuragtyagi1111]

When God come to help poor students ❤️

[@jePastapuramNagashwini]

in the next while loop, i replaced the while loop with for loop and it was not showing correct results but I don't understand y

[@mallikarjunpidaparthi]

Excellent and clear explanation. Thank you.

[@alpha183_i]

Thank you mam

[@hemanthreddy2485]

like bubble sort

[@nishantchandel7367]

how merge function return value as it above declared with void data type

[@snehagoyal3738]

In case of array , whatever changes are made in the array are inflicted in the original array itself that is arr[], we need not return anything. Changes are made in the original array only.

[@coder9009]

Thanks a lot for this video

[@anaskaratela7171]

any better approach than this while using functions in recursive way??

[@deepjyotikoley8499]

for better time complexity use quick sort

[@unknown__8874]

I got the code, but why did she use 'l' and 'r' ??

[@darshantrivedi5390]

Thanks 🔥☺️

[@csminor7456]

Can you please add Theory as well in the notes provided in the desciption

[@tarungupta5496]

No

[@search_Adam_seeker]

No

[@hazard30us76]

ye th even number of elements pe kaam ni kr rha hai...

[@abhishekhkumar11]

I didn't understand the time complexity part

[@zackcarl7861]

Why is the size of temporary array (mid-L+1)

[@VishalGupta-oh7mb]

0th to midth...inclusive

[@jyothishkamal8255]

Suggestion: please use comments to explain what the variables are

[@thetypicalone2525]

Sorry ur eplanation was right ,😙😙😙😙😙😅😅😅👍👍👍👌I was doing in the wrong way

[@sagarjain4128]

output blank aaraha hai. Can anyone help please

[@harshsharma4670]

I am having segmentation fault while running this code can anyone help??

[@kartikey14]

aced it...!!❤

[@surajalwayslight5707]

Bhaiya yeh code mere system main toh kuch aur hin result de raha aise kaise

[@revanthmahindra]

NOTES PLEASE

[@mancunianswagger3668]

It is important for us not gonna lie but this is hard. If it wasn't this important most of us would've skipped this right???

[@piyush5255]

my time complexity is coming out O(n log(2n))

[@myhp8300]

Why initializing k as 0 not giving the right answer? Help please

[@magicmartens11]

Because k is the iterator for arr[] array which starts from l and end at r.

[@jayashreeam7996]

I aam getting error for above code int[ int ] isbnot possible for array subscript for line a[ i ] = are[ l+i] please solve my ddoubt I am having my placement exam

[@d3vev]

14:00

[@lifeatovarun]

I will like apna college only when it will rectify the isssue.

[@prafulraghorte6189]

I have copied same code , but it's not running, frustrated af 😑

[@vibhashkumar5554]

Only legends know video length is 17:10 ,before the video premiere

[@niladriroy1665]

Kaise bata rha hai bhai tu?

[@mohammadejaz540]

Kaise?

[@II_xD_II]

define "legend"

[@neerajkrishnan8574]

@@II_xD_II map ke icons ko identify krne waaala chart lol

[@ishankbansal9239]

diii we can do it with only one array toooo

[@movieshub4922]

Sound problem.. Beech beech mae volume km hoo jaati hai

[@user-ld3ny2yp2y]

Please put hindi in the description or smtn, I got really confused by the intro lmao

[@purnimamishra3819]

Please help me to make the lecture on the topic of computer organization and architecture 🙏🏻

[@dhairyashah5886]

classic video!!!!!

[@alisaquibraza6870]

why is there no base case for recursion?

[@mayurcm271]

The code is not proper it is giving wrong output

[@yogendrarajput5929]

Test Cases Not included-- Code is Below---> void merge(int input[], int low, int mid, int high){ int b[high-low+1]; int l1=low,l2=mid+1,i=0; while(l1

[@onimthestrongest6229]

Nice

[@mdminhaj8567]

Thank you so much sister for your informative speech.