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

[@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 😅😅😅😅

[@mrpandey7312]

thanks to all who created this free of cost course

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

[@sleepypanda7172]

her voice!!! too sweet! Great explanation!

[@BEESaiShivam]

87k views and only 2.5k likes shows that this series is not for beginners but for who already know the basics!!!!

[@shishirshekhar]

yes

[@IFYatharthAurangpureIT]

very correct

[@Lack_Of_Enemies]

bhai lekin sorting to beginner stuff h

[@BEESaiShivam]

@@Lack_Of_Enemies rhne do bhai ab fms me pdta hu cat 99.5% lol maa chudaye coding

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

[@nithinshukla4679]

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

[@AbdUllah-m2j3j]

Only one of you can teach me correctly so proud you

[@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?

[@rutvikrana512]

Mergesort vs quicksort Quicksort will give average time complexity of O(N*log(N)) and worst case O(N*N) But mergesort gives best case as well as average case complexity O(n *log(n)) It means mergesort will not take less than this time but in average case it will be n log(n)... so if your array is small, you will still need this much time, but qsort is much faster for smaller size array because it can take O(N) in sorted array while mergesort will take n log(n) for this. So quicksort is faster than mergesort. So why use mergesort ? It is used to know inversion count. Qsort :- Fast and used in small arrays Mergesort :- stable and used for big arrays and linked list.

[@veeresh4441]

Could u tell what is inversion count ?

[@rutvikrana512]

@@veeresh4441 ... inversion count is numbers of swaps needed to sort an array. We can easily count swaps in bubble sort also. But if we need less time complexity than we can use merge sort algorithm.

[@abhigujjar7439]

Not average, quicksort bestcase is O(nlogn)

[@rutvikrana512]

@@abhigujjar7439 ... yes and no. It’s about practical results. In practice, average time of qsort is less than mergesort. Read in a book, I didn’t practice myself though 😂

[@abhigujjar7439]

According to books the average and best case for quick sort is O(nlogn)

[@Annu_Chaudhary2004]

Best m best ma'am 10 marks sure ho gye isse pdh kr thanks 🙏👍

[@AmanTheDisciple]

Awesome video, thanks for the easy explanation! :)

[@WinaTechnologies]

it was a verry good video, yet , consider using meaningfull variable names , i mean a[i] = arr[l + i] seems confusing isnt it ? avoid using variable names like a and b instead use for example left_array and right_array or whatever the key point is using meaningfull variable names , otherwise i see the explanation was just clear thank you so much ❤❤❤

[@code-a-mania4100]

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

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

[@maheriyajatinbharatbhai3538]

thanks for this amazing playlist!

[@anujjadhav2771]

I am in love with this series ❤

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

[@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😶

[@subratadas8408]

Explained well thanks .

[@samridhisaini6147]

explanation is just so clear

[@maazahmed6634]

Microsoft Wali didi is helping Pakistanis as well❤️

[@ashishbohare8864]

Love u didi 😘 bdiya pdhaya

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

[@rohandhale9766]

Best explaination Of Logic And TimeComplexity

[@leenagupta7801]

wow... Nicely explain....

[@subratakundu732]

Thanks didi for good explanation with less time.

[@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 ???

[@aayushsharma5133]

Super animation🔥🔥

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

[@Special_moment_]

very good explanation . I really enjoyed.

[@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 😀😀

[@abdulkareemabid2132]

kal exam hai aur bahi kasam se iss se jayada madad mujhe kine nahi ke thanks a lot sis

[@harshal.rathore]

there could be a much better explanation the animation didn't help much in understanding the flow of whole code

[@sambhavgandhi6553]

true

[@shahriar5570]

Give me a video link if you found a better explanation for the code.. I actually need it

[@mallikarjunpidaparthi]

Excellent and clear explanation. Thank you.

[@pankaj.yadav1]

Ma'am bhut axa smjhati h

[@aswinbarath]

🔥🔥🔥Verithanam🔥🔥🔥

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

[@anantsinghal3180]

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

[@nikunjjain5212]

@Nikunj Manhas thanks Nikunj 😂

[@Tenohekabanzai]

if this programme was Apple, Neha maam would be Siri We want Neha maam in all videos :) :) :)

[@PulkitMalhotra]

1no. Content 🔥

[@khuramkhalid5396]

THANK YOU SO MUCH!!

[@mdminhaj8567]

Thank you so much sister for your informative speech.

[@faizansaqeeb3390]

Amazing👍😍🤩

[@tarun-prakash]

AMAZING ROCKET SCIENCE

[@avijitdey6998]

Great explanation maam, it's clear all of my doubts

[@dhobi-the-tiger-69]

Love dey. 🤡

[@vaibhav7453]

Take input from user

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

[@nishantyadav7461]

Aman bhaiya ❤️❤️❤️❤️❤️❤️ I want to know the concept of Int**arr =new*arr

[@vrajeshmodi4928]

if you want to pass 2D array in any function you have to assign int** arr /*pointer*/ = new *[n] /* your main arr of size n */;

[@subhammishra316]

@@vrajeshmodi4928 thanx bro

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

[@krishnaanasurya3549]

Thx for Desi explanation , Ghusenge ghusenge...

[@anuragtyagi1111]

When God come to help poor students ❤️

[@lakshtrivedi004]

Can we get backtracking part 2?

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

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

[@priyanshuhazarika9968]

A smaller function is below. merge function is reduced void merge(int arr[], int l, int mid, int r) { int n1 = mid - l + 1; int n2 = r - mid; // different from video --> one extra element int a[n1 + 1]; int b[n2 + 1]; //maximize the extra element a[n1]=INT_MAX; b[n2]=INT_MAX; 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; // different from video --> using or ( || ) while (i < n1 || j < n2) { if (a[i] < b[j]) { arr[k] = a[i]; k++; i++; } else { arr[k] = b[j]; k++; j++; } } }

[@zackcarl7861]

What is array size (mid-l+1)

[@amitkumarlkr]

Int arr ko apne void function me kaise change kar diya array ka to sirf value jata hai nai dusre function me ????

[@rohitsaini7427]

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

[@coder9009]

Thanks a lot for this video

[@ishitabisaria6437]

Sir notes of this lecture??

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

[@jyothishkamal8255]

Suggestion: please use comments to explain what the variables are

[@kimjongun2217]

Thumbnail dek k hi samj aa gya🔥🔥🔥

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

[@virendraverma5855]

Function Mergesort how it working samajh nahi aaya

[@vatsalpoddar6660]

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

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

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

[@imranimmu4714]

expecting better explanation for time complexity

[@ambujsharma7642]

Could you please explain merge sort example with ecmascript 6

[@AkashKumar-lg5po]

You beat Abdul Bari explanation . Wowwwww

[@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🤐

[@thetypicalone2525]

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

[@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);"

[@twodimensions459]

This code is not fully optimized.. it is showing time limit exceeded

[@dhairyashah5886]

classic video!!!!!

[@chanduchandrakanth5131]

Is mergesort sort itself

[@vinayakjalan5696]

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

[@alpha183_i]

Thank you mam

[@kartikey14]

aced it...!!❤

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

[@anaskaratela7171]

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

[@deepjyotikoley8499]

for better time complexity use quick sort

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

[@puneetfanspage]

ma you telling the code in right way but you don't understand us the clear topic when you teach us that in merge function that int n1= mid-l+1 you just telll us but you don't cleariy that so please understand this song this is the feed back of all video because you doing same mistake all in this video i'm not blame you i appreciate your experience but please ensure that before teaching that are this topic is really i know and i will teach this with very clearification thanks mam for this code

[@Dont_know_wt]

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

[@Dont_know_wt]

@@harshitrathi3077 acha

[@subodhsingh9287]

when 2 and 8 are merged then we should get 8 and 2 .RIGHT??? but slides shows 2 and 8 at 3:18

[@animegod5295]

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

[@_rahulsain]

animation se time complexity smj aaygi

[@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???

[@darshantrivedi5390]

Thanks 🔥☺️

[@bhimashankarhalasage2267]

Why we passing mid to merge?

[@iffattuli8676]

Thanks! :)

[@rivines]

Ma'am aap thoda tez bolti to shi rhta

[@oqant0424]

thanx a bunch

[@hemant-li1gp]

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

[@StoryGicRohit]

shukriya

[@sabyasachidas4572]

Can you just tell me why n1=mid-l+1??

[@patil_ji]

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

[@djpro6413]

mam we have to lesan the synatx of code of n1 and n2 otherwise how this logic is made😡 😡

[@rewatkarshiven675]

what is the logic of n1=mid-l+1