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

[sohebshaikh]

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

[mrpandey]

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.

[eros]

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

[sleepypanda]

her voice!!! too sweet!
Great explanation!

[nithinshukla]

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

[sajankumarkar]

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<=mid && j<=h)
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=mid)
temp[k++]=a[i++];
while(j<=h)
temp[k++]=a[j++];

// Storing the values in the original array

for(i=l; i<=h; i++)
a[i]=temp[i-l];// cuz we have to go from temp[0] to temp[1] to....and i-l=0 for the 1st.
}

[rutvikrana]

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.

[BEESaiShivam]

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

[AbdUllah-mjj]

Only one of you can teach me correctly so proud you

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

[pritishpattnaik]

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.

[code-a-mania]

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

[Annu_Chaudhary]

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

[shubhamkale]

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

[shaktirajsinhzala]

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

[artirani]

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

[harshitnema]

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;

[rohandhale]

Best explaination Of Logic And TimeComplexity

[sjr]

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